Deleting the Nth Node from the End of a Linked List in One Pass
The dummy-head and fast-slow gap technique turns a two-pass linked-list problem into a clean one-pass solution with no special-case branches. It’s a reusable template for any interview or production scenario where you need to act on a position relative to the list’s end.
The standard two-pass approach—counting the list length, then deleting—is replaced by a single traversal using a dummy node and two pointers. The dummy node, prepended to the original list, ensures every real node has a predecessor, so deleting the head requires no special handling. The fast pointer moves n steps ahead first, creating a fixed gap; both pointers then advance together until fast hits the last node. At that point, slow sits exactly before the node to remove.
A single `slow.next = slow.next.next` line cuts the target node out of the list. Returning `dummy.next` always yields the correct new head, even when the original head was deleted. The algorithm runs in O(L) time and O(1) space.
Common failure points include skipping the dummy node, writing `while(fast)` instead of `while(fast.next)`, and mistakenly returning the original head after it has been removed. The pattern generalizes to any linked-list problem requiring a one-pass operation relative to the list’s end.
The dummy-head pattern is underused in everyday code but eliminates entire categories of null-pointer and edge-case bugs in linked-list manipulation.
Many developers instinctively reach for a two-pass solution (count then delete) because they don’t immediately see that a fixed pointer gap can encode the offset from the end.
The same fast-slow gap technique applies to finding the kth-from-end element, rotating a list, or detecting cycles—it’s a general positioning primitive, not just a deletion trick.