Learn more about Russian war crimes in Ukraine.

How to remove duplicates from an unsorted linked list

Question 2.1 of Cracking the Coding Interview:

Write code to remove duplicates from an unsorted linked list. How would you solve this problem if a temporary buffer is not allowed?

Here’s a solution in C:

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

typedef struct Node {
  int val;
  struct Node * next;
} Node;

Node* mk_node(int val, Node* next) {
  Node* node = malloc(sizeof(Node));
  node->val = val;
  node->next = next;
  return node;

Node* rm_vals(int val, Node* list) {
  if (list != NULL) {
    list->next = rm_vals(val, list->next);
    if (list->val == val) {
      Node* ret = list->next;
      return ret;
    } else {
      return list;
  } else {
    return NULL;

Node* rm_dups(Node* list) {
  if (list != NULL) {
    list->next = rm_vals(list->val, list->next);
    list->next = rm_dups(list->next);
    return list;
  return list;

int main(int argc, char** argv) {
  Node* node_5 = mk_node(5, NULL);
  Node* node_4 = mk_node(3, node_5);
  Node* node_3 = mk_node(2, node_4);
  Node* node_2 = mk_node(5, node_3);
  Node* node_1 = mk_node(5, node_2);

  node_1 = rm_dups(node_1);

  assert(node_1->val == 5);
  assert(node_1->next->val == 2);
  assert(node_1->next->next->val == 3);
  assert(node_1->next->next->next == NULL);

  assert(rm_dups(NULL) == NULL);

  return 0;

This is O(n^2). I don’t see a way to improve on this without using extra memory, which the question doesn’t allow.

What can computers do? What are the limits of mathematics? And just how busy can a busy beaver be? This year, I’m writing Busy Beavers, a unique interactive book on computability theory. You and I will take a practical and modern approach to answering these questions — or at least learning why some questions are unanswerable!

It’s only $19, and you can get 50% off if you find the discount code ... Not quite. Hackers use the console!

After months of secret toil, I and Andrew Carr released Everyday Data Science, a unique interactive online course! You’ll make the perfect glass of lemonade using Thompson sampling. You’ll lose weight with differential equations. And you might just qualify for the Olympics with a bit of statistics!

It’s $29, but you can get 50% off if you find the discount code ... Not quite. Hackers use the console!

More by Jim

Tagged #ctci, #programming, #c. All content copyright James Fisher 2020. This post is not associated with my employer. Found an error? Edit this page.