Coding Prep
Remove Nth Node From End of List
n-step head start: advance fast by n nodes first, then move both until fast reaches the tail - slow lands at the node just before the target, enabling O(1) deletion.
Problem
Remove the nth node from the end of a linked list and return the modified head. Do it in one pass.
Input: 1->2->3->4->5, n=2 → 1->2->3->5 (remove 4th node = 2nd from end)
Input: 1, n=1 → [] (remove the only node)
Input: 1->2, n=1 → 1 (remove the tail)Solution
Approach: Two pointers with a fixed n-step offset, anchored by a dummy head.
You cannot walk backward in a singly linked list, so instead create a constant gap and let it convert "nth from the end" into a position you can reach going forward. Put a dummy before the head and start both fast and slow there. Advance fast by n + 1 steps. That +1 is the whole trick: it leaves slow not on the target but one node before it, which is exactly what deletion needs since unlinking requires the predecessor's next. Now move fast and slow together until fast falls off the end (while fast). The n + 1 gap is preserved the entire way, so when fast becomes None, slow sits on the target's predecessor. Splice the target out with slow.next = slow.next.next and return dummy.next.
Trace [1,2,3,4,5], n=2. Start fast=slow=dummy. Advance fast three steps to node 3. Move together: slow=1,fast=4; slow=2,fast=5; slow=3,fast=None, stop. slow.next is 4, so slow.next = slow.next.next skips it, giving [1,2,3,5].
Edge cases: Removing the head (n equals the list length) is handled with no special branch - slow stays on dummy, and dummy.next is rewired, so returning dummy.next yields the new head. A single-node list with n=1 returns None the same way.
Complexity: O(L) time, O(1) space - one pass over L nodes, a handful of pointers.
Done reading? Mark it so it sticks in your dashboard.