Removing Duplicates from a sorted linked list

#algorithms #computerscience #dsa #tutorial

*Removing Duplicates from a Sorted Linked List
*
Linked lists are an important data structure, and a common problem is removing duplicate elements. When the linked list is already sorted, this problem becomes much easier because duplicate values appear next to each other.

Understanding the Problem

Given a sorted linked list like:

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

We need to remove duplicate nodes so that the final list becomes:

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

Since the list is sorted, duplicates will always be adjacent. This property allows us to solve the problem in a single pass.

*Approach Used
*
We use a simple traversal technique:

Start from the head of the list
Compare each node with its next node
If they are equal, skip the next node
Otherwise, move forward

This approach modifies the list in place and does not require extra memory.

Code
def removeDuplicates(head):
    current = head

    # Traverse the list
    while current and current.next:
        if current.data == current.next.data:
            # Skip the duplicate node
            current.next = current.next.next
        else:
            # Move to the next distinct node
            current = current.next

    return head

**Step-by-Step Explanation

Initialize Pointer**

current = head

We start from the head of the linked list. The current pointer is used to traverse the list.

2. Traverse the List
while current and current.next:

We continue looping as long as:

current is not null current.next is not null

This ensures we can safely compare the current node with the next node.

3. Check for Duplicate
if current.data == current.next.data:

Since the list is sorted, duplicates will be adjacent. If both values are equal, it means we found a duplicate.

4. Remove Duplicate
current.next = current.next.next

Instead of moving forward, we skip the duplicate node by changing the pointer.

This effectively removes the duplicate node from the list.

5. Move to Next Node
else: current = current.next
If the current node and next node are different, we simply move forward.

Example Walkthrough

Consider the list:

1 --> 1 --> 2 --> 3 --> 3
Start at first node (1)
Compare with next (1), duplicate found, skip it
Move to next distinct node (2)
Compare 2 with 3, not duplicate, move forward
Compare 3 with 3, duplicate found, skip it

Final list becomes:

1 --> 2 --> 3
Why This Approach is Used

This method is efficient because:

It takes advantage of the sorted property
It removes duplicates in a single traversal
It does not require extra space
It modifies the list in place

Without sorting, we would need additional data structures like sets or hash maps.

Key Insight

The most important idea is that sorting guarantees duplicates are adjacent. This allows us to detect and remove duplicates by comparing only neighboring nodes.

Time and Space Complexity