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.
I just released Vidrio,
a free app for macOS and Windows to make your screen-sharing awesomely holographic.
Vidrio shows your webcam video on your screen, just like a mirror.
Then you just share or record your screen with Zoom, QuickTime, or any other app.
Vidrio makes your presentations effortlessly engaging, showing your gestures, gazes, and expressions.
#1 on Product Hunt.
Available for macOS and Windows.
With Vidrio
With generic competitor
More by Jim
- Your syntax highlighter is wrong
- Granddad died today
- The Three Ts of Time, Thought and Typing: measuring cost on the web
- I hate telephones
- The sorry state of OpenSSL usability
- The dots do matter: how to scam a Gmail user
- My parents are Flat-Earthers
- How Hacker News stays interesting
- Project C-43: the lost origins of asymmetric crypto
- The hacker hype cycle
- The inception bar: a new phishing method
- Time is running out to catch COVID-19
- A probabilistic pub quiz for nerds
- Smear phishing: a new Android vulnerability
Tagged #ctci, #programming, #c. All content copyright James Fisher 2020. This post is not associated with my employer. Found an error? Edit this page.