Remove Nth Node From End of List

Delete the node that sits n positions from the tail of a linked list, then return the list's head, which changes when the node removed is the first one.

Example: 1 -> 2 -> 3 -> 4 -> 5, n = 2. Remove 4. Result: 1 -> 2 -> 3 -> 5.

1. Iterate through the list to find the total length L.
2. The node to remove is at index L - n (from start).
3. Iterate again to the node just before L - n and change its next pointer.

This works but requires traversing the list twice.

Can we do this in One Pass? Imagine a stick of length n. If we slide this stick along the list so the front end touches the last node, the back end will be exactly at the node we need to remove!

1. Create a dummy node pointing to head (to handle removing the first node easily).
2. Move a fast pointer n + 1 steps ahead.
3. Move both fast and slow (initially at dummy) until fast reaches null.
4. slow is now pointing at the node before the target.
5. Delete target: slow.next = slow.next.next.

Watch fast open a gap of n + 1 nodes from dummy, then both pointers slide until fast is NULL — leaving slow just before the node to remove. The removed node ends up in its own row, reachable from nothing.