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.

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

Jim Fisher

TigYog

Speaking

CV

Blogroll

RSS