Friday, October 25, 2013

Deleting duplicates from a sorted linked list

Given a sorted linked list, We have to delete all the duplicates in that list. For example, If we get the following list

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

The output should be

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

To solve this problem we take two pointers current and next, we iterate through the list until the next pointer reaches the end of the list.

In each iteration we compare the data at current and next nodes. If they are equal, we delete the next node, and the next pointer is advanced to the subsequent node. Take a look at the pictorial representation of this step to understand better.

Here is the working code of C++ for this.