Remove duplicate nodes in a singly linked list.

To remove duplicate in singly linked list firstly, to delete any node in a singly linked list, we need to have its previous node handle. Secondly, we need to identify the next node is duplicate or not.

We will use a map to identify the next node duplicate or not by having the current node handle, which is previous to the next node. Let us see this approach step by step.

Initially, we insert ten into the map and then set next to 10s next and current to 10. Now we check 14 on the map, as it does not exist in it. We insert that into the map and jump to its next nodes.
Now next node ‘7’ also not in map, so we insert that into map and jumps to their next nodes.
‘3’ is not in the map, so inserting that into map and jumping to their respective next nodes.
As ’10’ already exists in the map, we just ignore that and jumps to its next. Then we set current next as new next node as showing here. For memory, we can keep duplicate node ’10’ in a temp node and free it later.
As ‘3’ also exists in the map, we ignore that and moves next to its next node, and the next of the current node now set to the next node. As next reaches to NULL, the algorithms ends here.

Finally, our linked list becomes 10->14->7->3->NULL, as showing in the above picture. Let us see this approach with a C program.

void removeDuplicates(Node *head)
{
    Node *next = head->next;
    Node *curr = head;
    unordered_map<int, bool> dupMap;
    dupMap[curr->data] = true;
    while (next)
    {
        if (dupMap.find(next->data) != dupMap.end())
        {
            Node *tmp = next;
            next = next->next;
            curr->next = next;
            free(tmp);
        }
        else
        {
            dupMap[next->data] = true;
            next = next->next;
            curr = curr->next;
        }
    }
    curr->next = NULL;
}

This methods runs with a complexity O(N). Complete code with main function is in below gist.

// Output
10  14  7  3  10  3  7  8  14  
10  14  7  3  8 

It is all about removing duplicates in a singly linked list using a hash map, which runs with a linear complexity. If you know any better approach to solve this problem, please comment below to help our readers. Happy Learning.