Learn › DSA Patterns › Fast and Slow Pointers › Case Study
Remove Nth Node From End:
4 Bugs to a Clean Solution
Not a tutorial — a real debugging log. Five attempts, four distinct bugs, each one reproduced with a concrete failing input before it was fixed.
The Problem
LeetCode 19 — Remove Nth Node From End of List
Given the head of a singly linked list, remove
the nth node from the end of the list
and return its head — in a single pass.
Input
[1,2,3,4,5], n=2 Output
[1,2,3,5] Input
[1], n=1 Output
[] Input
[1,2], n=1 Output
[1] The Journey
Attempt by Attempt
Every bug below was reproduced with a real failing input before being fixed — not just described.
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
let dummy = head;
let slow = dummy, fast = dummy;
for (let i = 0; i < n; i++) fast = fast!.next;
while (fast!.next) {
slow = slow!.next;
fast = fast!.next;
}
slow!.next = slow!.next!.next;
return dummy!.next;
}`dummy` is just another name for `head` — the same node object, not a fresh predecessor.
A dummy node exists specifically so `slow` always has somewhere valid to sit even when the node being removed is the first one. Aliasing `dummy = head` throws that guarantee away — for a single-node list, advancing `fast` past the (fake) dummy runs off the end of the list entirely.
Proof — input [1], n=1:
dummy = head = Node(1). slow = fast = dummy. for i=0: fast = fast.next = null. while(fast.next) → fast is null → fast.next throws. Expected: [] (empty list). Got: TypeError — Cannot read properties of null (reading 'next').
Use a real placeholder node — `new ListNode(0, head)` — so `slow`/`fast` always start one position before the real list, giving every node (including the head) a genuine predecessor.
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
const dummy = new ListNode(0, head);
let slow = dummy, fast: ListNode | null = dummy;
while (0 < n) { fast = fast!.next; }
while (fast!.next) {
slow = slow!.next;
fast = fast!.next;
}
slow!.next = slow!.next!.next;
return dummy.next;
}The loop meant to walk `fast` forward `n` times checks `0 < n` — but nothing inside the loop body ever changes `n`.
`while (0 < n)` reads like it was meant to be a countdown, but the decrement got dropped. `fast` keeps calling `.next` forever, either hanging or eventually crashing once `fast` walks past the end of the list into `null.next`.
Proof — input [1,2,3,4,5], n=2:
Loop body runs unconditionally (n is never touched): fast → 1 → 2 → 3 → 4 → 5 → null, then null.next → CRASH after 6 iterations. Condition `0 < n` was never even re-checked meaningfully — n stayed 2 the whole time. Infinite loop / crash — expected [1,2,3,5].
Use a bounded loop that actually consumes `n`: `for (let i = 0; i < n; i++) fast = fast.next;`
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
const dummy = new ListNode(0, head);
let slow = dummy, fast: ListNode = dummy;
for (let i = 0; i < n; i++) fast = fast.next!;
while (fast.next) {
slow = slow!.next!;
fast = fast.next;
if (fast.next) {
slow.next = slow.next!.next;
}
}
return dummy.next;
}The removal line works — but it's nested inside `if (fast.next)` inside the loop, so it runs once per iteration instead of exactly once, after the loop finishes.
This isn't a syntax error, so it silently produces a wrong list instead of crashing. Because the condition is true on almost every pass, the splice (`slow.next = slow.next.next`) fires repeatedly against a `slow` pointer that's still advancing — each firing permanently skips whatever node `slow` was pointing at in that moment, not just the intended target.
Proof — input [1,2,3,4,5], n=2:
gap: fast→2, slow stays at dummy iter1: slow→1, fast→3. fast.next(4) truthy → splice: 1.next=2.next=3 → dummy→1→3→4→5 (2 wrongly removed!) iter2: slow→3, fast→4. fast.next(5) truthy → splice: 3.next=4.next=5 → dummy→1→3→5 (4 wrongly removed too!) iter3: slow→5, fast→5. fast.next=null → no splice. loop ends. Returns [1,3,5] (WRONG — expected [1,2,3,5]; two nodes removed instead of one)
Move the removal out of the `if` and out of the loop entirely — run it once, unconditionally, right after the `while` finishes.
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
const dummy = new ListNode(0, head);
let slow = dummy, fast: ListNode = dummy;
for (let i = 0; i < n; i++) fast = fast.next!;
while (fast.next) {
slow = slow!.next!;
fast = fast.next;
slow.next = slow.next!.next;
}
return dummy.next;
}
// removal still lives inside the loop — if the loop body never runs (0 iterations), it never firesThe `if` is gone, but the removal is still the last statement inside the `while (fast.next)` loop body — so it only ever runs if the loop body runs at least once.
For most inputs the loop runs multiple times, masking the defect. But when the target to remove is close enough that the loop body never executes even once — e.g. removing the only node in a 1-element list — the removal never fires at all.
Proof — input [1], n=1:
dummy→1. slow = fast = dummy. for i=0: fast = dummy.next = Node(1). while(fast.next): fast.next = Node(1).next = null → loop body never runs (0 iterations). Removal line never executes. Returns dummy.next = Node(1), unchanged. Returns [1] (WRONG — expected [], the only node was never removed)
Pull the removal all the way out of the loop — after the `while`, unconditional, exactly once — so it fires the same way regardless of how many times (including zero) the loop body ran.
// O(N) time, O(1) space — two-pointer gap + dummy node
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
const dummy = new ListNode(0, head);
let slow: ListNode = dummy, fast: ListNode = dummy;
for (let i = 0; i < n; i++) fast = fast.next!; // open the n-node gap
while (fast.next) { // walk together until fast is on the last node
slow = slow.next!;
fast = fast.next;
}
slow.next = slow.next!.next; // single, unconditional removal
return dummy.next; // never head — it may have been the removed node
}
// [1,2,3,4,5], n=2 → [1,2,3,5]
console.log(removeNthFromEnd(list1, 2)); // → [1,2,3,5]
// [1], n=1 → [] (no crash, no skipped removal)
console.log(removeNthFromEnd(list2, 1)); // → []Advance `fast` a fixed `n` steps ahead of `slow` from the dummy. Walk both forward together until `fast` is on the last real node. `slow` is now exactly one node before the target — splice it out once, unconditionally, after the loop. Return `dummy.next`, never `head` — `head` itself may have just been removed.
Proof — both cases verified:
[1,2,3,4,5], n=2 → [1,2,3,5] ✅ (node 4 removed, no over-removal) [1], n=1 → [] ✅ (0-iteration loop still triggers the unconditional removal after it)
Interactive
Gap Visualizer
Watch the n=2 gap slide down [1,2,3,4,5] step-by-step.
fast starts at dummy and advances n=2 steps: dummy→1→2. slow stays at dummy.
Lessons Learned
Key Takeaways
A dummy node is required whenever the target might be the head
Aliasing dummy = head isn't a shortcut — it throws away the entire reason a dummy node exists. slow needs a real predecessor node even when the node being removed is the original head.
Bound your loops with something that actually changes
while (0 < n) with nothing decrementing n is a condition that's permanently true. A for loop with an explicit counter makes the bound impossible to forget.
Operations meant to happen once, at the end, don't belong inside a loop's if
Burying slow.next = slow.next.next inside an if inside the while loop meant it fired once per qualifying iteration instead of exactly once — silently corrupting the list instead of crashing.
Zero-iteration loops are a real edge case — test them
Removing the only node in a 1-element list means the second while loop's body never runs at all. Any logic still living inside that loop, even unconditionally, gets skipped entirely.
Final Result
The Verified Solution
Two-pointer gap + dummy node — a single pass, no second traversal to find the length.
// O(N) time, O(1) space — two-pointer gap + dummy node
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
const dummy = new ListNode(0, head);
let slow: ListNode = dummy, fast: ListNode = dummy;
for (let i = 0; i < n; i++) fast = fast.next!; // open the n-node gap
while (fast.next) { // walk together until fast is on the last node
slow = slow.next!;
fast = fast.next;
}
slow.next = slow.next!.next; // single, unconditional removal
return dummy.next; // never head — it may have been the removed node
}
// [1,2,3,4,5], n=2 → [1,2,3,5]
console.log(removeNthFromEnd(list1, 2)); // → [1,2,3,5]
// [1], n=1 → [] (no crash, no skipped removal)
console.log(removeNthFromEnd(list2, 1)); // → []| Solution | Time | Space | Verified |
|---|---|---|---|
| Two-Pointer Gap + Dummy Node (Attempt 5) Verified ✓ | O(N) | O(1) | Multi-node and single-node (0-iteration) cases, single pass |
Reuse This
Template: Two-Pointer Gap + Dummy Node
The generic shape behind this solution — adapt it to any "Kth from the end" problem on a linked list.
function nStepGapWithDummy(head, n):
dummy = new Node(placeholder)
dummy.next = head
slow = dummy
fast = dummy
for i in 0..n-1:
fast = fast.next // open a fixed n-node gap
while fast.next is not null:
slow = slow.next
fast = fast.next // walk together — gap stays constant
// slow is now exactly one node before the target
performOperation(slow) // e.g. slow.next = slow.next.next
return dummy.next // never return head — it may have been the targetWhen to reach for this
Kth-from-the-end problems on a singly linked list, or any operation that might need to modify/remove the head.
The trap this journey hit
Operations meant to happen once, at the end, get buried inside an if inside the loop instead — making them fire an unpredictable number of times.
Test Yourself
Quiz: Check Your Understanding
Your score
0 / 12
Keep Learning
Bugs are part of the process 🎉
Four real bugs, four real fixes — that's what getting to a correct, single-pass Two-Pointer Gap solution actually looks like.