The O(n) Club: Remove Linked List Elements – How a Dummy Node Keeps You Sane

The O(n) Club: Remove Linked List Elements – How a Dummy Node Keeps You Sane

⚡ TL;DR

Your mission: rip every node containing val out of a singly linked list, head included, without writing a choose-your-own-adventure for edge cases. Brute force is a pointer shuffle, elegantly saved with a dummy node. Quick n’ dirty Java:

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}
 // Remove Linked List Elements
ListNode removeElements(ListNode head, int val) {
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    ListNode prev = dummy, curr = head;
    while (curr != null) {
        if (curr.val == val) {
            prev.next = curr.next;
        } else {
            prev = curr;
        }
        curr = curr.next;
    }
    return dummy.next;
}

🧠 How Devs Usually Mess This Up

If you’ve ever written five lines just to check if head should be deleted, congratulations—you’re not alone. Most folks:

• Forget heads can be removed, so they litter their code with while (head != null && head.val == val) and invite bugs to the party.
• Advance prev even when they delete, causing phantom nodes or memory black holes—spooky.
• Pretend Java needs manual memory hacking. Newsflash: Just break the chain and the GC sweeps up your old junk like a Roomba after a toddler’s birthday.

🔍 What’s Actually Going On

Imagine your linked list is a suspiciously long guest list at a party. Some guests (nodes) need to go—their name (val) is on the no-entry list. But what if the very first name, or every second guest, is banned? Enter the dummy node, your bouncer buddy. It guards the door, stands in for the head, and never complains. You breeze down the list, quietly removing troublemakers, and when the party’s over, dummy simply points to the new crowd. Simple. Elegant. Zero drama.

The magic: you adjust prev.next to skip current troublemakers. Only advance prev when you keep a guest. No need to check if your party starts with no one (empty list) or only troublemakers. GC gets any node you drop—no basement full of ghosts like in C++.

🛠️ PseudoCode

• Create a dummy node before head
  

  ListNode dummy = new ListNode(-1);
  dummy.next = head;

  Start everything with dummy in charge.
• Set prev and curr pointers
  

  ListNode prev = dummy;
  ListNode curr = head;

  The dynamic duo: prev for the last real node, curr for what you’re currently interrogating.
• Walk through the list:
  

  while (curr != null) { ... }

  Don’t stop until you hit null.
• If curr.val matches target, cut it out
  

  if (curr.val == val) {
      prev.next = curr.next;
  }

  Don’t move prev—let it point to the next possible survivor.
• If it doesn’t match, keep it
  

  else {
      prev = curr;
  }

  Move prev up to follow the good node.
• Always move curr
  

  curr = curr.next;

  Keep the interview rolling.
• Return dummy.next
  

  return dummy.next;

  The new head—could be your old one, or not.

💻 The Code

// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}
 public class RemoveLinkedListElements {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode prev = dummy, curr = head;
        while (curr != null) {
            if (curr.val == val) {
                prev.next = curr.next;
            } else {
                prev = curr;
            }
            curr = curr.next;
        }
        return dummy.next;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• When your whole list is the target: dummy.next is null, and you’re done—no tears required.
• Prev pointer addiction: Only move prev when you actually keep a node.
• Infinite loops: Fiddling with pointers without solid logic gets you a personal Groundhog Day.
• Performance: O(n) time (every guest gets a handshake), O(1) space (just pointers and one dummy—for Java, memory’s cheap).

🧠 Interviewer Brain-Tattoo

“Dummy nodes: If you’re not using them, enjoy debugging your code at 2 a.m.”