Remove Nth Node From End of List (LeetCode 19)
Your input is a linked list's head plus an integer n. Delete the node that sits n positions from the end of the list, then return the (possibly new) head.
Follow up: Can you find and delete that node in one pass, without first counting the list's length?
Worked Examples
head = [1,2,3,4,5], n = 2[1,2,3,5]head = [1], n = 1[]head = [1,2], n = 1[1]⚖️Formal Constraints & Bounds
The number of nodes in the list is
sz.1 <= sz <= 300 <= Node.val <= 1001 <= n <= sz
Core Insight
A dummy node plus a lead pointer that starts n nodes ahead of the trail pointer puts the trail pointer on the node before the target, even when the target is the head.
Real-World Scenario & Production Applications
LRU cache tail invalidation, packet queue tail trimming, and undo-history fixed-depth truncation.
Step-by-Step Execution Trace Table
| Phase | lead pos | trail pos | Action |
|---|---|---|---|
| Dummy Init | Dummy | Dummy | dummy = ListNode(0, head), then lead and trail both start on dummy |
| Open The Gap | Node 2 (moved n = 2 steps) | Dummy | Only lead moves, so it is n nodes ahead of trail |
| Move Together | Node 5 (last node) | Node 3 | Both move one node per step, so the gap stays n; the loop stops when lead.next is empty |
| Unlink | Node 5 | Node 3 | trail.next = trail.next.next (Node 4 is removed) |
| 1 | dummy = ListNode(0, head) |
| 2 | lead = trail = dummy |
| 3 | for _ in range(n): |
| 4 | lead = lead.next |
| 5 | while lead.next: |
| 6 | lead = lead.next |
| 7 | trail = trail.next |
| 8 | trail.next = trail.next.next |
| 9 | return dummy.next |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
You can't count backward from the end of a singly linked list — there's no way to peek at length - n. So this trick never counts from the end at all.
🚶🚶 The Analogy: Walking a Fixed-Length Rope Between Two Hikers
Imagine two hikers connected by a rope that is exactly n steps long. Both start at the same place, on the dummy node. The lead hiker walks n steps alone, which pulls the rope tight. From then on, both hikers walk forward together, one step at a time, and the gap stays n steps. The lead hiker stops on the last node of the trail. The trailing hiker is then n steps behind, which is the node just before the one you need to remove.
🔑 The Key Idea in the Code
The dummy node at the very start exists purely so "the node before the head" is a real, addressable node too — letting the exact same gap-walk logic remove the head itself without a special case.
Deleting head node without a dummy sentinel: If
n == len(list), removing the nth node from the end removeshead. Without adummy.next = headsentinel, you lose the list reference.Pairing the gap with the wrong loop test:
trailmust stop on the node immediately PRECEDING the target. Withwhile lead.next:the gap isn; withwhile lead:the gap would have to ben + 1. Mixing them removes the wrong node.Memory leak by not severing deleted node: In languages with manual memory management (C++/C#), forgetting to free or detach the deleted node causes a memory leak.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Single-pass deletion relative to linked list tail.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: lead is exactly n nodes ahead of trail during the whole walk.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Deleting the head node: always use a dummy node pointing to head to prevent null pointer exceptions.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I create a dummy node before head and start lead and trail on it. I move lead n nodes ahead, then I move lead and trail together until lead.next is empty. The gap stays n, so trail is now on the node before the target, and I set trail.next = trail.next.next. I return dummy.next. It runs in
O(N)time andO(1)space."
Complexity & Mathematical Proof
O(L)
Look at the execution steps: lead moves n nodes ahead of trail, then both pointers move one node per step until lead.next is empty. lead visits each node at most once, so the walk is one pass of at most L steps. trail is then on the node before the target.
O(1) Auxiliary
Look at memory allocations: the code is iterative, so the call stack stays constant. It stores one dummy node and the two references lead and trail, which is O(1) space.
T(L) = L + 1 node steps = O(L)
Derivation Progression
n initial hops
Moves lead n nodes from the dummy node while trail stays on it.
L - n synchronous hops
Both pointers advance together until lead.next is empty.
trail.next = trail.next.next
Node is unlinked in O(1) pointer updates.
Variable Definitions
Total number of nodes in the linked list
Position of the node to remove, counted from the end of the list (1 is the last node)
Memory Architecture & Bounds
O(1) Iterative
O(1) Dummy node and 2 pointers
O(1) Head reference
Boundary Best / Worst Cases
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "remove n-th node from end of list", "do this in one pass". Fixed-distance lead pointer pattern.
. Single-pass time and memory.
Removing the head node (when ). The sentinel dummy node absorbs head deletion uniformly without special branching.
Remove Nth Node From End of List (LeetCode 19)
Your input is a linked list's head plus an integer n. Delete the node that sits n positions from the end of the list, then return the (possibly new) head.
Follow up: Can you find and delete that node in one pass, without first counting the list's length?
Worked Examples
head = [1,2,3,4,5], n = 2[1,2,3,5]head = [1], n = 1[]head = [1,2], n = 1[1]⚖️Formal Constraints & Bounds
The number of nodes in the list is
sz.1 <= sz <= 300 <= Node.val <= 1001 <= n <= sz
Core Insight
A dummy node plus a lead pointer that starts n nodes ahead of the trail pointer puts the trail pointer on the node before the target, even when the target is the head.
Real-World Scenario & Production Applications
LRU cache tail invalidation, packet queue tail trimming, and undo-history fixed-depth truncation.
Step-by-Step Execution Trace Table
| Phase | lead pos | trail pos | Action |
|---|---|---|---|
| Dummy Init | Dummy | Dummy | dummy = ListNode(0, head), then lead and trail both start on dummy |
| Open The Gap | Node 2 (moved n = 2 steps) | Dummy | Only lead moves, so it is n nodes ahead of trail |
| Move Together | Node 5 (last node) | Node 3 | Both move one node per step, so the gap stays n; the loop stops when lead.next is empty |
| Unlink | Node 5 | Node 3 | trail.next = trail.next.next (Node 4 is removed) |
| 1 | dummy = ListNode(0, head) |
| 2 | lead = trail = dummy |
| 3 | for _ in range(n): |
| 4 | lead = lead.next |
| 5 | while lead.next: |
| 6 | lead = lead.next |
| 7 | trail = trail.next |
| 8 | trail.next = trail.next.next |
| 9 | return dummy.next |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
You can't count backward from the end of a singly linked list — there's no way to peek at length - n. So this trick never counts from the end at all.
🚶🚶 The Analogy: Walking a Fixed-Length Rope Between Two Hikers
Imagine two hikers connected by a rope that is exactly n steps long. Both start at the same place, on the dummy node. The lead hiker walks n steps alone, which pulls the rope tight. From then on, both hikers walk forward together, one step at a time, and the gap stays n steps. The lead hiker stops on the last node of the trail. The trailing hiker is then n steps behind, which is the node just before the one you need to remove.
🔑 The Key Idea in the Code
The dummy node at the very start exists purely so "the node before the head" is a real, addressable node too — letting the exact same gap-walk logic remove the head itself without a special case.
Deleting head node without a dummy sentinel: If
n == len(list), removing the nth node from the end removeshead. Without adummy.next = headsentinel, you lose the list reference.Pairing the gap with the wrong loop test:
trailmust stop on the node immediately PRECEDING the target. Withwhile lead.next:the gap isn; withwhile lead:the gap would have to ben + 1. Mixing them removes the wrong node.Memory leak by not severing deleted node: In languages with manual memory management (C++/C#), forgetting to free or detach the deleted node causes a memory leak.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Single-pass deletion relative to linked list tail.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: lead is exactly n nodes ahead of trail during the whole walk.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Deleting the head node: always use a dummy node pointing to head to prevent null pointer exceptions.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I create a dummy node before head and start lead and trail on it. I move lead n nodes ahead, then I move lead and trail together until lead.next is empty. The gap stays n, so trail is now on the node before the target, and I set trail.next = trail.next.next. I return dummy.next. It runs in
O(N)time andO(1)space."
Complexity & Mathematical Proof
O(L)
Look at the execution steps: lead moves n nodes ahead of trail, then both pointers move one node per step until lead.next is empty. lead visits each node at most once, so the walk is one pass of at most L steps. trail is then on the node before the target.
O(1) Auxiliary
Look at memory allocations: the code is iterative, so the call stack stays constant. It stores one dummy node and the two references lead and trail, which is O(1) space.
T(L) = L + 1 node steps = O(L)
Derivation Progression
n initial hops
Moves lead n nodes from the dummy node while trail stays on it.
L - n synchronous hops
Both pointers advance together until lead.next is empty.
trail.next = trail.next.next
Node is unlinked in O(1) pointer updates.
Variable Definitions
Total number of nodes in the linked list
Position of the node to remove, counted from the end of the list (1 is the last node)
Memory Architecture & Bounds
O(1) Iterative
O(1) Dummy node and 2 pointers
O(1) Head reference
Boundary Best / Worst Cases
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "remove n-th node from end of list", "do this in one pass". Fixed-distance lead pointer pattern.
. Single-pass time and memory.
Removing the head node (when ). The sentinel dummy node absorbs head deletion uniformly without special branching.