Remove Duplicates From Linked List

Category

Linked Lists

Difficulty

Easy

Problem Statement

Given the head of a singly linked list whose nodes are sorted in ascending order, remove all duplicate nodes so that each value appears only once. Return the modified linked list (which is still sorted).

Intuition

Since the list is sorted, all duplicate values are adjacent. We can traverse the list with a single pointer: if the current node's value equals the next node's value, we skip the next node by updating the pointer. Otherwise, we advance to the next node.

Approach

1. Start with a pointer at the head of the list.
2. While the current node and the next node both exist:
   • If the current node's value equals the next node's value, set current.next = current.next.next (skip the duplicate).
   • Otherwise, move the pointer forward: current = current.next.
3. Return the head.

Pseudocode

function removeDuplicates(head):
    current = head
    while current is not null:
        while current.next is not null and current.value == current.next.value:
            current.next = current.next.next
        current = current.next
    return head

Time & Space Complexity

• Time: O(n) where n is the number of nodes. Each node is visited at most once.
• Space: O(1) — the removal is done in place with only a single pointer.

Key Insights

• The sorted order guarantee is critical — it ensures duplicates are contiguous, so a single pass suffices.
• We modify the next pointers to skip duplicates rather than deleting nodes explicitly.
• A nested while loop handles runs of multiple duplicates (e.g., 1 -> 1 -> 1 -> 2), but the total work across all iterations is still O(n).

Edge Cases

• Empty list (head is null): return null.
• Single-node list: no duplicates possible; return the head.
• All nodes have the same value: the result is a single-node list.
• No duplicates in the list: the list is returned unchanged.
• Duplicates only at the end of the list.