Remove Nth Node From End of List

Given the head of a linked list, remove the n-th node from the end of the list and return its head.

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 the gap of size n slide to the end of the list.