The O(n) Club: Remove Duplicates from Sorted List II (aka Everybody Out!)

The O(n) Club: Remove Duplicates from Sorted List II (aka Everybody Out!)

⚡ TL;DR

Given a sorted linked list, kick out everyone who dares show up more than once. Any value with a clone? Gone. Only solo flyers remain. You’ll want a dummy node for stress relief (and boundary cases). Here’s the slow way—don’t use it in interviews, unless you love pain:

// Brute-force (O(n^2) and painful):
public ListNode deleteDuplicates(ListNode head) {
    Set
<integer> seen = new HashSet<>();
    Set
<integer> dupes = new HashSet<>();
    for (ListNode curr = head; curr != null; curr = curr.next)
        if (!seen.add(curr.val)) dupes.add(curr.val);
    ListNode dummy = new ListNode(0, head), prev = dummy, curr = head;
    while (curr != null) {
        if (dupes.contains(curr.val)) prev.next = curr.next;
        else prev = curr;
        curr = curr.next;
    }
    return dummy.next;
}</integer></integer>

🧠 How Devs Usually Mess This Up

Don’t make the classic mistake: just trimming down duplicates so each value only appears once. Interviewers want total elimination—if you see a number twice, it’s radioactive. Also, skipping the dummy node is like showing up to a chainsaw juggling contest in flip-flops; not recommended, especially if the deleted nodes are at the head. And please, stop writing solutions as if the list might be unsorted. The problem’s one gift is that it’s sorted. Take it!

🔍 What’s Actually Going On

Imagine a club so exclusive that if anyone else shares your name, everyone with your name gets denied entry. The bouncer (dummy node) never blinks. Because the list is sorted, all the doppelgängers are huddled together, easy for the bouncer to spot and boot out in one sweep. Two pointers—one to keep order, one to check IDs—patrol the list. No mercy. If they find twins, everybody’s out, and only the loners make it past the velvet rope.

🛠️ PseudoCode

• Initialize dummy node: Dummy points to head; it’s your invisible club manager.
• Set two pointers: prev at dummy, current at head (the current guest).
• While current exists:
  • If current’s value equals current.next’s value: You found the party crashers.
  • Skip them all: Save their value; advance current until the value changes.
  • prev.next now points to current (skipping the disqualified batch).
  • If no duplication detected, both pointers just quietly advance one step each.
• Return dummy.next as your result list—if anyone’s left.

// Java-ish pseudocode
ListNode dummy = new ListNode(0, head);
ListNode prev = dummy, curr = head;
while (curr != null) {
    if (curr.next != null && curr.val == curr.next.val) {
        int dupe = curr.val;
        while (curr != null && curr.val == dupe) curr = curr.next;
        prev.next = curr;
    } else {
        prev = prev.next;
        curr = curr.next;
    }
}
return dummy.next;

💻 The Code

// ListNode definition for Java
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
 public ListNode deleteDuplicates(ListNode head) {
    ListNode dummy = new ListNode(0, head);
    ListNode prev = dummy, curr = head;
    while (curr != null) {
        if (curr.next != null && curr.val == curr.next.val) {
            int dupe = curr.val;
            while (curr != null && curr.val == dupe) curr = curr.next;
            prev.next = curr;
        } else {
            prev = prev.next;
            curr = curr.next;
        }
    }
    return dummy.next;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• If the head is a repeat value, only that dummy node stands between you and disaster.
• Empty/null lists: If you blow up on these, your interviewer will frown—sort it out, champ.
• All values are duplicates? Output is null (club’s empty—there goes the night).
• Time is O(n) (each person only checked twice, no matter how awkward the conversation); space is O(1) (unless you count your emotional baggage).

🧠 Interviewer Brain-Tattoo

“When everyone’s special, no one is. But on this list, only the truly unique get in. Consider your dummy node your velvet rope.”