Remove Duplicates in Sorted Linked List

This problem is about cleaning up a linked list. I was given a sorted linked list, and the task was to remove duplicate nodes so that each value appears only once.

At first glance, it looked simple, but I wanted to understand why the sorted property makes this problem easier and how to solve it without using extra space.

Understanding the Problem

We are given a singly linked list where elements are already sorted.

Example:

2 -> 2 -> 4 -> 5
Expected output:
2 -> 4 -> 5

Another case:
2 -> 2 -> 2 -> 2 -> 2

Output:
2

So the idea is simple:
If a value repeats, keep only one occurrence
Remove the rest

Why Do We Need to Remove Duplicates?

While working with data structures, duplicates can cause unnecessary repetition and increase memory usage.

In real scenarios:
Duplicates can lead to incorrect results in searching or processing
They make the structure less efficient
Clean data is always easier to work with

Since the list is already sorted, all duplicate values appear next to each other. This makes it much easier to detect and remove them.

My Initial Thought

At first, I thought of using a set to track seen values:

Traverse the list
Store values in a set
Remove duplicates

But this uses extra space, which the problem suggests avoiding.

So I tried to solve it using only pointers.

Key Observation

Because the list is sorted:

All duplicate elements are adjacent,This means I only need to compare a node with its next node.

Approach

I used a single pointer and traversed the list.
At each step:

Compare current node with next node
If they are equal → skip the next node
If not → move forward

Steps

Start from the head
While current node and next node exist:
If current.data == current.next.data:
Remove next node by linking current to next.next
Else:
Move current forward
Continue until the end

Algorithm

    def removeDuplicates(self, 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