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