Remove Nth Node From End of List

Given the head of a singly linked list, remove the nth node counting from the end and return the head. The machine must find that node in a single pass — without first computing the list length, and without storing nodes in an array.

The key insight: hold two pointers exactly n nodes apart. Advance fast by n steps first; then walk slow and fast together. When fast reaches the end, slow sits on the node before the target — because the target is n nodes from the end, the gap means the predecessor is n + 1 from the end.

Approach:

1. Use a dummy node before head so removing the first node is not a special case.
2. Advance fast n steps ahead of slow.
3. Walk both until fast is None; then rewire slow.next = slow.next.next.

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

Time: O(n), one pass. Space: O(1).

Trickiest edge case: removing the head itself — without the dummy sentinel, slow would have no predecessor to rewire, so the dummy exists precisely to make that case identical to all others.