Given the head of a linked list and an integer n, remove the n-th node counting from the END — n = 1 is the last node — and return the head. The follow-up everybody gets: do it in one pass.
Examples
Example 1:
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
Example 2:
Input: head = [1], n = 1
Output: []
Example 3:
Input: head = [1,2], n = 2
Output: [2]
Explanation: removing the head is the case that breaks pointer-only solutions.
Example 4:
Input: head = [1,2], n = 1
Output: [1]
Constraints
1 <= list length <= 30
1 <= n <= list length
0 <= Node.val <= 100
Prerequisites
Linked lists — a node holds a value and a next reference, and rearranging a list means moving references, never values. Dummy heads: a node in front of the list so the first element stops being a special case. Two pointers on a list — one ahead of the other, or one moving twice as fast.
How to think about it
1. Two Pointers, n Apart Optimal
Intuition
Counting from the end is counting from the start once you know the length — but the follow-up asks for one pass, and a gap of n does it: send one pointer ahead by n, then move both until the leader falls off. The trailer is now exactly one node before the target. Starting both at a dummy head makes deleting the actual head the same move as any other, which is the case that breaks solutions that skip it.
Algorithm
1. Put a dummy node in front and start both pointers there. 2. Advance the lead pointer n steps. 3. Move both until the lead reaches the last node. 4. Unlink the node after the trailing pointer. 5. Return dummy.next.