Remove Nth Node From End of List
Remove the n-th node from the end of the list and return the head — ideally in one pass.
- The number of nodes in the list is sz.
- 1 <= sz <= 30
- 0 <= Node.val <= 100
- 1 <= n <= sz
Intuition
Remove nth node from end of list deletes a node counted from the tail, in a singly linked list that can only be walked forwards.
The two-pass solution measures the length, then walks to position length − n. Correct and clear. The follow-up asks for one pass, and the technique is a fixed gap between two pointers:
- Advance one pointer n nodes ahead, then move both together — when the leader reaches the end, the follower is exactly n nodes from it.
The gap never changes once established, so the follower's position relative to the tail is fixed from the start.
Deletion needs the node before the target, so the follower must stop one short. Advancing the leader n + 1 steps instead of n achieves that, and this off-by-one is the crux of the problem.
A dummy node before the head is what makes it work cleanly. Removing the first node is otherwise a special case with no predecessor to relink — with a dummy, every node including the head has one:
Return dummy.next rather than head, since the head may itself have been deleted.
The problem guarantees n is valid, so the leader never runs past the end unexpectedly. Without that guarantee, a null check during the initial advance would be needed.
Removing the only node in a single-element list works correctly through the dummy, returning null.
One pass with two pointers gives O(n) time and O(1) space — the same time as the two-pass version, with half the traversal.
A fixed gap rather than a speed difference: advance one pointer n steps, then move both together — when the leader hits the end, the follower sits exactly n from the back. The dummy node is the other half of the trick, making removal of the head need no special case at all.
Approach
Before reading on: price up what counting everything costs here, then ask which pointers must be saved before you overwrite anything. Aim for O(L) time and O(1) space.
Establish a fixed gap
Advance one pointer ahead of the other and keep the distance constant. The follower's position relative to the tail is then fixed from the moment the gap is set.
Use a dummy node
Place a dummy before the head so every node has a predecessor. Removing the first node is otherwise a special case with nothing to relink.
Advance n + 1, not n
Deletion needs the node before the target, so the follower must stop one short. This off-by-one is the crux of the problem.
Move both together
Advance both pointers one step at a time until the leader reaches the end. The follower then sits just before the node to remove.
Unlink the target
Set follower.next = follower.next.next, bypassing the node. A single-element list resolves correctly through the dummy.
Return the dummy's next
Return dummy.next, not head — the original head may have been the node deleted.
Cost of the approach
One pass with two pointers gives O(n) time and O(1) space, halving the traversal of the two-pass version.
Solution & live demo
Common pitfalls
Starting both pointers at head instead of dummy
slow = fast = head
dummy = ListNode(0, head) slow = fast = dummy
Removing the head itself then requires slow to sit before it, which doesn't exist. The dummy gives every node a predecessor, so one code path handles head and interior nodes alike.
Advancing the leader n+1 times
for _ in range(n + 1):
fast = fast.nextfor _ in range(n):
fast = fast.nextCombined with the while fast.next loop, an extra step leaves slow one node too far along and deletes the wrong node. The gap and the loop condition must be chosen together — n steps with fast.next, or n + 1 steps with fast.
Looping while fast rather than fast.next
while fast:
slow = slow.next
fast = fast.nextwhile fast.next:
slow = slow.next
fast = fast.nextRunning until fast is null carries slow one position past the predecessor, so slow.next.next skips the wrong node — or raises on the last element.
Edge cases
The dummy node lets slow stop before the head, so removing the first node needs no special case.
After fast's head start it is null; slow stays on the dummy and unlinks the only node, returning an empty list.
fast walks to the last node; slow stops one before, splicing out the final node cleanly.