Given a singly linked list node, remove nodes with duplicate values while maintaining relative order of the original list.
Constraints
n ≤ 100,000 where n is the number of nodes in nodeExample 1:
Input: 1 – 1 – 2 – 2
Output: 1 – 2Example 2:
Input: 0 – 0 – 0
Output 0
How to Remove Duplicates in Linked List?
We can use O(N) hash set to achieve O(1) insert and lookup. We need to keep a previous pointer, and if a node has been inserted into the hash set before, we need to skip the node.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | /** * class LLNode { * public: * int val; * LLNode *next; * }; */ LLNode* removeDuplicatesLinkedList(LLNode* node) { unordered_set<int> vis; LLNode* dummy = new LLNode(-1); dummy->next = node; LLNode* prev = dummy; while (node) { if (vis.count(node->val)) { prev->next = node->next; } else { vis.insert(node->val); prev = node; } node = prev->next; } return dummy->next; } |
/**
* class LLNode {
* public:
* int val;
* LLNode *next;
* };
*/
LLNode* removeDuplicatesLinkedList(LLNode* node) {
unordered_set<int> vis;
LLNode* dummy = new LLNode(-1);
dummy->next = node;
LLNode* prev = dummy;
while (node) {
if (vis.count(node->val)) {
prev->next = node->next;
} else {
vis.insert(node->val);
prev = node;
}
node = prev->next;
}
return dummy->next;
}The space complexity is O(N), the time complexity is O(N) where N is the number of the nodes in the linked list. We use a dummy node to point to the head at the begining – which is to make the implementation a bit prettier without having to deal with the edge cases.
–EOF (The Ultimate Computing & Technology Blog)
loading...
Last Post: Teaching Kids Programming - Hexadecimal Numbers Conversion
Next Post: Complete an Arithmetic Sequence by Finding Missing Number
