19. Remove Nth Node From End of List

Advance a fast pointer n nodes ahead of a slow pointer, then move both together. When fast reaches the end, slow sits exactly on the node before the one to remove — so unlink it in a single pass.

Idea

To find the nth node from the end in one pass, keep two pointers exactly n nodes apart. When the leading pointer falls off the end, the trailing pointer is n from the end — positioned just before the node to delete.

A dummy node in front of the head elegantly handles the edge case of removing the very first node (no special-casing).

Algorithm

1. Create dummy -> head; set fast = slow = dummy.
2. Advance fast by n steps.
3. Move fast and slow together until fast.next is None. Now slow is the node before the target.
4. Unlink: slow.next = slow.next.next.
5. Return dummy.next.

Worked example: list 1→2→3→4→5, n = 2

• fast advances 2 → points at node 2.
• Move both until fast is the last node (5): fast walks 2→3→4→5, slow walks dummy→1→2→3. slow is at node 3.
• slow.next is 4 (the 2nd from the end) → skip it: 3→5.

Result: 1→2→3→5.

Complexity

• Time: O(sz) — a single pass.
• Space: O(1).

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode fast = dummy, slow = dummy;
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}