Removing Duplicates from a Sorted Linked List

Removing Duplicates from a Sorted Linked List

Problem

You’re given a sorted linked list, and the task is to remove duplicate nodes so that each value appears only once.

---

Strategy

The key detail here is that the list is already sorted.

At first, I thought about using extra space to track seen values, but that’s unnecessary. Because the list is sorted, any duplicates will always be right next to each other.

So the approach becomes simple:

• Traverse the list once
• Compare each node with the next one
• If they’re equal, remove the next node
• Otherwise, move forward

It’s more about adjusting pointers than actually “deleting” anything.

---

Code

def removeDuplicates(head):
    current = head

    while current and current.next:
        if current.data == current.next.data:
            current.next = current.next.next
        else:
            current = current.next

    return head

Key Lines Explained

• current = head
  Start from the beginning of the list.

• while current and current.next:
  We keep going as long as there’s a next node to compare with.

• if current.data == current.next.data:
  This is where we detect a duplicate.

• current.next = current.next.next
  Instead of deleting a node, we just skip it by changing the pointer.
  The duplicate node is effectively removed from the list.

• else: current = current.next
  If there’s no duplicate, we move forward normally.

Why This Works

Since the list is sorted:

• All duplicates are grouped together
• We never need to look ahead beyond one node
• A single pass is enough

This avoids unnecessary complexity and keeps the solution efficient.

Complexity

• Time: O(n) — we traverse the list once
• Space: O(1) — no extra memory is used

Final Note

This problem felt tricky until I focused on the “sorted” part.

Once that clicked, the solution became straightforward. It’s less about removing elements and more about carefully updating links between nodes.