Remove Nth Node From End of List
The problem
Remove the nth node counted from the end of a singly linked list and return the new head. Assume 1 ≤ n ≤ the list length.
Example
1 → 2 → 3 → 4, n = 2 becomes 1 → 2 → 4
Need a hint?
Use two pointers separated by a fixed gap.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Start both pointers at a dummy node before the head. Advance fast n + 1 links, then advance both until fast is null. Slow now precedes the node to remove. Set slow.next to slow.next.next and return dummy.next; this also handles removing the head.
Complexity
O(n) time and O(1) space, where n here denotes list length.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.