Remove Nth Node From End of List

Remove the n-th node from the end of a linked list in one pass and return the head.

A way to picture it

You can't see the end of the tunnel, so you send a scout n steps ahead on a rope of fixed length. Then you both walk at the same speed. When the scout touches the far wall, you're standing exactly n steps from the end.

How to approach it

Start two pointers at a dummy node. Move fast n steps, then move both until fast is on the last node. slow is right before the target.

Example

Input: {"head":[1,2,3,4,5],"n":2}. Output: [1,2,3,5].

Complexity: O(n) time and O(1) space. A single pass with a fixed gap.

This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.