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

Download   Run Code

Output:

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

Java

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

avatar
  Subscribe  
Notify of