Remove Nth Node From End

Remove Nth Node From End of List looks like it needs two passes — one to count the length, one to delete. The slick trick is a pair of pointers a fixed gap apart that gets it done in a single pass.

The slow way first

The obvious plan is two passes: walk the whole list once to get its length L, then walk again and stop at node number L - n to relink past the target. That works and is O(n) time, but it touches the list twice and the index math (L - n, off-by-one with the head) is fiddly.

The question to ask: can I find the nth-from-last node without first knowing the length? Yes — with a gap.

The idea: two pointers a fixed gap apart

Send a fast pointer n + 1 steps ahead of a slow pointer, then move both together until fast runs off the end (reaches None). Because the gap never changes, when fast is at the end, slow is sitting exactly one node before the one to delete — so slow.next is the target, and we relink past it.

We also add a dummy node in front of the head. That way the node to delete is never the real head, so removing the first node is just an ordinary relink — no special case.

The key insight: the constant gap turns "nth from the end" into "where slow lands when fast falls off."

Walk through it

Step through the animation. fast and slow both start on the dummy. fast advances 3 hops (n + 1 = 3) to build the gap. Then both move together until fast reaches NULL. At that moment slow is on node 3, so slow.next is 4 — the node to remove. We point slow.next straight at 5 and return dummy.next.

Pseudocode

dummy -> head                     # guard so the head is never a special case
fast = slow = dummy
repeat n + 1 times:               # build a gap of n + 1 nodes
    fast = fast.next
while fast is not None:           # walk both until fast runs off the end
    fast = fast.next
    slow = slow.next
slow.next = slow.next.next        # skip the target node
return dummy.next                 # the (possibly new) head

The Python solution

def remove_nth(head, n):
    dummy = ListNode(0, head)
    fast = slow = dummy
    for _ in range(n + 1):
        fast = fast.next
    while fast:
        fast = fast.next
        slow = slow.next
    slow.next = slow.next.next
    return dummy.next

• The dummy node points at the real head, so deleting the first node needs no special case.
• The first loop pushes fast n + 1 nodes ahead — that extra + 1 is what leaves slow before the target instead of on it.
• The while loop moves both pointers in lockstep, so the gap stays fixed until fast becomes None.
• slow.next = slow.next.next unlinks the target by pointing around it.
• We return dummy.next because the head itself may have been the node removed.

Complexity

Both are O(n) time, but the two-pointer version makes a single pass and uses only O(1) extra space — just two pointers and a dummy node.

When this pattern shows up

Practice