CA 23 - Remove Duplicates in Sorted Linked List

Problem

Given a sorted linked list, the task is to remove duplicate nodes such that each element appears only once.

The list should remain sorted and the operation should be done in-place.

Output

Example 1
Output: 2 -> 4 -> 5
Example 2
Output: 2

My Approach

To solve this problem, I used a single traversal method.

Since the linked list is already sorted, duplicate elements will be adjacent.

I traverse the list and compare each node with its next node:

If both values are equal, I skip the next node by changing the pointer
Otherwise, I move to the next node

I continue this process until the end of the list.

This works because in a sorted list, duplicates always appear next to each other, so we can remove them in one pass without extra space ().

This approach is efficient because:

It requires only one traversal
It uses constant extra space
Code

def remove_duplicates(head):
    curr = head
    while curr and curr.next:
        if curr.data == curr.next.data:
            curr.next = curr.next.next
        else:
            curr = curr.next
    return head