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;
      free(list);
      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.

This page copyright James Fisher 2020. Content is not associated with my employer. Found an error? Edit this page.

Jim Fisher

CV

Speaking

Blogroll

RSS

Granola