DSA problem
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.
The difficulty here is that a singly linked list can only be traversed forward, yet the target is described relative to the end. A straightforward two-pass solution first counts the total length L, then walks L - n nodes from the front to reach the node before the one to delete. This is correct and simple, but it scans the list twice.
The single-pass solution maintains a fixed n-node gap between two pointers. Advance a fast pointer n steps ahead first. Then move fast and a slow pointer together until fast reaches the last node; at that moment slow is exactly the predecessor of the node to remove, because the gap between them equals n.
To handle the case where the head itself must be removed, start both pointers from a dummy node placed before the head. The dummy guarantees slow always has a valid predecessor to rewire, so the deletion is a uniform O(1) pointer splice. The entire algorithm runs in one O(L) pass with O(1) extra space.
Examples
head = [1,2,3,4,5], n = 2[1,2,3,5]head = [1], n = 1[]head = [1,2], n = 2[2]Constraints
- The number of nodes in the list is sz.
- 1 <= sz <= 30
- 0 <= Node.val <= 100
- 1 <= n <= sz
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.