Remove duplicates from a sorted linked list

Given a linked list sorted in increasing order, write a function which removes any duplicate nodes from the list by traversing the list only once.

 

For example,

If the list is {1, 2, 2, 2, 3, 4, 4, 5}, it should be converted to {1, 2, 3, 4, 5}.

 


 

Since the list is sorted, we can proceed down the list and compare adjacent nodes. When adjacent nodes are the same, remove the second one. There’s a tricky case where the node after the next node needs to be noted before the deletion.

 
C++ implementation –
 

Download   Run Code

Output:

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

 
Source:
http://cslibrary.stanford.edu/105/LinkedListProblems.pdf

 
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
wpDiscuz