19. Remove Nth Node From End of List
You receive the head of a singly linked list (each node has a val and a next pointer) and an integer n. Delete the node that sits n-th from the end — n = 1 means the tail, n equal to the length means the head — and return the head of the resulting list.
n is always valid: 1 <= n <= length of the list. Deleting the only node of a one-element list leaves an empty list (return None/null).
The follow-up worth chasing: can you do it in one traversal of the list?
Example 1:
Input: head = [3, 8, 2, 7, 5], n = 2
Output: [3, 8, 2, 5]
Explanation: Counting from the tail, node 1 is 5 and node 2 is 7 — so the node holding 7 is unlinked and 2 now points at 5.
Example 2:
Input: head = [6], n = 1
Output: []
Explanation: The list has a single node and n = 1 removes it, leaving an empty list.
Constraints:
- 1 ≤ length of the list ≤ 3 * 10⁴
- -1000 ≤ node value ≤ 1000
- 1 ≤ n ≤ length of the list
Hints:
Counting from the end is awkward in a singly linked list — but if the length is L, the target is simply node number L − n + 1 from the front. That costs two passes.
For one pass, run two pointers with a fixed gap: send `fast` ahead by n nodes, then walk `fast` and `slow` together until `fast` runs off the end — `slow` now stands on the node before the one to delete.
Deleting the head is the classic edge case. Start both pointers from a dummy node placed in front of the head and every deletion, including the head's, becomes the same `slow.next = slow.next.next` rewire.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: head = [3, 8, 2, 7, 5], n = 2
Expected output: [3, 8, 2, 5]