Remove duplicates from a linked list in single traversal

Given an unsorted linked list, write a function which deletes any duplicate nodes from the list by traversing the list only once.

 

For example,

Input:  5 -> 3 -> 4 -> 2 -> 5 -> 4 -> 1 -> 3 -> null
Output: 5 -> 3 -> 4 -> 2 -> 1 -> null

 


 

Simple solution would be to consider every distinct pair of nodes in the list and check if they have same data or not. If their data matches we delete the latter node. The time complexity of this solution is O(n2).
 

We can perform better by using hashing. The idea is to traverse the given list and insert each encountered node into a set. Now, if the current node already present in the set (i.e. it is seen before), we delete it and move to next element. At the end, we will have all duplicated removed from the list.

C++

Download   Run Code

Output:

5 -> 3 -> 4 -> 2 -> 1 -> null


 

The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).

 
Remove duplicates from a sorted linked list

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
speedplane
Guest
speedplane

I’m not going to take the bait, but I feel like the above algorithm can be written in five lines of python, which has built in hashed sets.

wpDiscuz