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.
Intuition
Counting from the end is awkward in a singly linked list. Give a fast pointer an n-node head start; when fast reaches the end, slow sits exactly on the node just before the one to remove.
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
Counting first means two passes
Position-from-the-end is awkward in a singly linked list because you can only move forward. The obvious fix — measure the length, then walk to length − n — works but takes two passes. We can do it in one by keeping a fixed gap between two pointers.
Build an n-node gap, then move together
Advance a fast pointer n steps first, so fast and slow are exactly n nodes apart. Now move both at the same speed until fast reaches the last node. Because the gap is preserved, slow ends up n nodes from the end — specifically, right before the node we want to remove. We converted 'nth from the end' into 'where fast stops,' which needs no length.
A dummy head handles removing the first node
If the target is the head itself, slow needs to stop 'before the head' — so we start both pointers on a dummy node placed before the head. After the walk, splice the target out with slow.next = slow.next.next and return dummy.next. The dummy makes head-removal and single-node lists work with no special case. One pass, O(L) time, O(1) space.
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.