The O(n) Club: Remove Nth Node From End—Don’t Lose Your Head (Literally)

The O(n) Club: Remove Nth Node From End—Don’t Lose Your Head (Literally)

⚡ TL;DR

Delete the nth node from the end of a singly linked list—no rearview mirror allowed! The brute force way? Count, then delete. The pro way? Two pointers, one dummy node, zero drama. Java below, coffee not included:

// Brute-force: two passes
int length = 0;
ListNode curr = head;
while (curr != null) { length++; curr = curr.next; }
curr = head;
for (int i = 0; i < length - n - 1; i++) curr = curr.next;
curr.next = curr.next.next;

🧠 How Devs Usually Mess This Up

Here’s where dreams go to die: you count nodes, math up a position, and try a casual pointer shuffle—only to delete the head or nuke the wrong node. Off-by-one bugs? You’ll have more than you have coffee mugs. Pro tip: “head” is not immortal, and neither is your code without a dummy node. Without it, welcome to a night of pointer purgatory and unresolved references.

🔍 What’s Actually Going On

Picture a line of robots passing memory sticks—no one can see who’s behind. Want to kick the nth robot from the end out the cargo hatch? You can march to the end and count, then walk again to evict. Or, let one robot stride ahead n+1 steps. As both “fast” and “slow” march together, when fast hits the airlock, slow’s finger hovers over the eject button—no rewiring, no time travel. And if your head gets popped? Dummy node repairs the chain before HR even notices.

🛠️ PseudoCode

• Install a dummy node before head:

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

  This handles the tragic ‘delete-the-head’ scenario. Heroic.

• Race fast pointer n+1 steps ahead:

  ListNode fast = dummy;
  for (int i = 0; i <= n; i++) fast = fast.next;

  So slow will be perfectly positioned for sniping.

• Stroll slow and fast together till fast falls off the end:

  ListNode slow = dummy;
  while (fast != null) {
    slow = slow.next;
    fast = fast.next;
  }

  Slow is now one node before the soon-to-be-gone culprit.

• Delete the suspect node:

  slow.next = slow.next.next;

  Cue disappearing act.

• Return dummy.next as the new head:

  return dummy.next;

  Critical if the head was disappeared.

💻 The Code

// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
 public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    ListNode fast = dummy;
    ListNode slow = dummy;
     // Fast gets n+1 steps ahead
    for (int i = 0; i <= n; i++) {
        fast = fast.next;
    }
     // Both pointers advance in sync
    while (fast != null) {
        slow = slow.next;
        fast = fast.next;
    }
     // Skip the dead node
    slow.next = slow.next.next;
    return dummy.next;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Deleting the head: When n equals the list’s length. That’s why dummy nodes = your new BFF.
• Single node lists: If n = 1, and list has one node, you’re about to delete everything. Brace for null.
• Off-by-one disaster: Move your fast pointer n+1 steps, not just n, or you’ll become an urban coding legend for all the wrong reasons.
• Don’t use recursion: Unless you enjoy spectacular stack overflows when your list is longer than your patience.
• Complexity check: Single pass: O(n). Space: O(1). Elegance: Infinite.

🧠 Interviewer Brain-Tattoo

“Dummy nodes: fixing pointer meltdowns since before you learned Java. Use one, sleep better.”