Remove Nth Node From End of List
The Prompt
Given the `head` of a linked list, remove the `n`-th node from the end of the list and return its head.
Understanding the Problem
"Nth from the end" is awkward for a singly linked list because you only discover where the end is after you have walked past everything. The two-pass fix — count the length, then walk again to node length − n — works but the interviewer wants one pass.
The one-pass trick is a fixed gap: send a fast pointer n + 1 steps ahead of slow (both starting at a dummy node before the head), then move the two pointers in lockstep. When fast steps off the end, slow is standing exactly one node before the victim — perfectly placed to unlink it.
The Interview Flow
Interviewer
How can you remove the Nth node from the end of a list in a single pass?
Candidate
A single pass suggests I can't first find the length and then iterate again. The two-pointer technique seems appropriate here.
Interviewer
Describe how you'd use two pointers.
Candidate
I'll use a `fast` pointer and a `slow` pointer. I will first advance the `fast` pointer `n` steps ahead. This creates a gap of `n` nodes between `fast` and `slow`.
Interviewer
What do you do after creating the gap?
Candidate
Then, I move both `fast` and `slow` pointers one step at a time until the `fast` pointer reaches the end of the list. At this point, the `slow` pointer will be positioned just before the node that needs to be removed.
Interviewer
So you can just update `slow.next`?
Candidate
Exactly. I can set `slow.next = slow.next.next` to bypass and effectively remove the desired node. There is an edge case to handle, though: if the node to be removed is the head itself. I can solve this by using a dummy node that points to the head, and starting my `slow` pointer there.
Interviewer
Using a dummy node is a great way to handle that edge case. Please implement this approach.
Why does a fixed gap land slow just before the target?
The invariant: fast stays exactly n + 1 nodes ahead of slow for the entire lockstep walk, because both move one step per tick. When fast becomes null (one past the last node), slow must be n + 1 nodes before null — that is, at the node immediately before the nth-from-the-end. One assignment, slow.next = slow.next.next, removes it.
Starting slow at a dummy node (not the head) is what makes the edge case free: if the head itself must be removed, slow ends up on the dummy and the same assignment works, then dummy.next is returned. One traversal, two pointers: O(L) time, O(1) space — the same asymptotics as two passes but half the walking, and the single-pass constraint satisfied.
One-Pass Solution with Two Pointers
- Create a `dummy` node and set `dummy.next = head`. This simplifies handling the edge case where the head needs to be removed.
- Initialize two pointers, `fast` and `slow`, both starting at the `dummy` node.
- Advance the `fast` pointer `n+1` steps. This is `n+1` because we started `slow` at the dummy node, so we need the gap to be `n` between `slow` and the node to be removed.
- Now, move both `fast` and `slow` pointers forward one step at a time, until `fast` becomes `null`.
- When `fast` is `null`, `slow` will be pointing to the node right before the one we need to remove.
- Perform the removal by updating the pointer: `slow.next = slow.next.next`.
- Return `dummy.next`, which is the head of the modified list.
Try it yourself
Write your solution and run it against 3 test cases.
JavaScript, TypeScript & Python run sandboxed in your browser; other languages run on the execution server. Your code is saved locally as you type.
Final Solution
function removeNthFromEnd(head, n) {
const dummy = new ListNode(0, head);
let left = dummy;
let right = head;
for (let i = 0; i < n; i++) {
right = right.next;
}
while (right) {
left = left.next;
right = right.next;
}
// delete
left.next = left.next.next;
return dummy.next;
}Explanation
Remove the 2nd node from the end of 1 → 2 → 3 → 4 → 5 (that is node 4) in a single pass.
1Both pointers start at the dummy. Advance fast n + 1 = 3 steps to node 3 — the gap between fast and slow is now fixed.
2Move both in lockstep 3 more steps: fast walks 4, 5, null; slow walks 1, 2, 3. Fast fell off, so slow (at 3) sits just before the victim, node 4.
3Unlink with slow.next = slow.next.next: 3 now points at 5, bypassing 4. Return dummy.next — the list is 1 → 2 → 3 → 5.
Complexity Analysis
TIME
O(n)
SPACE
O(1)
Finished working through this one?
Mark it complete to track it on your Data Structures path.