Remove Nth Node From End of List

Problem

You are given the head of a singly linked list and an integer n. Remove the node that is n-th from the end of the list (so n = 1 removes the last node) and return the head of the resulting list. Try to do it in a single traversal.

• The list has between 1 and 100 nodes.
• Node values fit in a signed 32-bit integer.
• n is between 1 and the number of nodes, inclusive.

Examples

• 6 -> 3 -> 9 -> 12 -> 15, n = 2 → 6 -> 3 -> 9 -> 15. The 12 is second from the end.
• 4, n = 1 → empty list. Removing the only node leaves nothing.
• 8 -> 2, n = 2 → 2. Removing the head must return the new head.

Hints

1. Counting the length first and then walking to position len - n works in two passes. What would you need to know during a single pass to stop at the right place?
2. If a second pointer is always exactly n nodes ahead of you, where are you when it falls off the end?
3. Use two pointers with a gap of n + 1 starting from a dummy node before the head, so the trailing pointer lands on the predecessor of the node to remove.