Algorithm to Remove Duplicates in Linked List using Hash Set

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 node

Example 1:
Input: 1 – 1 – 2 – 2
Output: 1 – 2

Example 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.

/**
 * 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)