The O(n) Club: Remove Duplicates from Sorted List – But Please, Don’t Use a HashSet

The O(n) Club: Remove Duplicates from Sorted List – But Please, Don’t Use a HashSet

⚡ TL;DR

Your ordered singly linked list is full of doppelgängers. All you need is a single pointer pass to ghost the extras. No rebuilding, no hash set hoarding—just classic pointer gymnastics:

// Brute force? Gonna cost you.
List<Integer> seen = new ArrayList<>();
ListNode node = head;
while (node != null) {
    if (!seen.contains(node.val)) seen.add(node.val);
    node = node.next;
}

🧠 How Devs Usually Mess This Up

When the hammer is arrays, every problem looks like a nail. People try copying values, rebuilding lists, slapping on a HashSet, or worse—resuscitating nodes by overwriting val (but undead nodes still lurk just off-screen). Others panic-scroll the list again and again, burning cycles and pride.

🔍 What’s Actually Going On

This is a sorted list: duplicated values huddle in little packs. You don’t need Sherlock. You need a bouncer with a sharp eye. When the current and next values match, cut the next node from the guest list by setting current.next = current.next.next. That’s it. No mess. No paper trail. Just clean, O(1) pointer hustle, and you’re done before the job gets boring.

🛠️ PseudoCode

• Set your curr at the head of the list.
• While curr != null && curr.next != null:
• If curr.val == curr.next.val, then curr.next = curr.next.next; (duplicate axed).
• Otherwise, move curr forward.
• Praise the algorithm gods for a one-pass, memory-lite win.

// Java snippet preview
ListNode curr = head;
while (curr != null && curr.next != null) {
    if (curr.val == curr.next.val) {
        curr.next = curr.next.next;
    } else {
        curr = curr.next;
    }
}

💻 The Code

// Java definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
 public ListNode deleteDuplicates(ListNode head) {
    ListNode curr = head;
    while (curr != null && curr.next != null) {
        if (curr.val == curr.next.val) {
            curr.next = curr.next.next;
        } else {
            curr = curr.next;
        }
    }
    return head;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Null pointer shenanigans: always check curr.next before using it—don’t let a stray null ruin your interview.
• Erasing val instead of skipping nodes doesn’t truly delete anything (just decorates the ghost).
• If list is empty or single-item: congrats, you’re already done.
• O(n) time, O(1) space—unless you sneak in a HashSet (don’t).

🧠 Interviewer Brain-Tattoo

“Linked lists: skip nodes, not sleep. Move pointers, not values. And check for duplicates in order.”