Removing Duplicates from Sorted Linked List

Problem Statement

You are given a singly sorted linked list, which has repeated elements. The task at hand is to remove the duplicates from the linked list.

Here is a diagram to explain the problem statement

Removing Duplicates from Sorted Linked List

Solution for Removing Duplicates from Sorted Linked List

As the linked list is sorted, if two nodes contain duplicates, they will always be adjacent to each other. Hence, the trick is to

  • Maintain two pointers (Current_Node_Ptr and Next_Node_Ptr).
  • If the Next_Node_Ptr points to a duplicate node, delete the node and advance the Next_Node_Ptr
    • Make the next of Current_Node_Ptr point to the Next_Node_Ptr after each deletion.
  • Else Advance the Current_Node_Ptr

As per the above algorithm, we have to use two loops, the outer loop advances the Current_Node_Ptr and the inner loop deletes duplicate node and advances the two pointers.

Source Code

To download the complete working code, check out github link.

Analysis

The running time of the algorithm is linear. We see two loops but if you look closely, each element of the linked list is just visited ones. Hence the running time is O(N)

We do not use any space except for one reference variable to store the Next_Node_Ptr.

Stay Subscribed and Keep Reading.