You are given head, the first node of a singly linked list, and a number n.
Remove the nth node counting from the end of the list (n = 1 is the last node), and return
the head of what remains. If the list had only one node, what remains is empty. Try to do it in
a single pass over the list.
Linked lists are written as their values from head to tail, so [1, 4, 6] is 1 → 4 → 6.
Example 1
- Input
- head = [10, 20, 30, 40, 50], n = 2
- Output
- [10, 20, 30, 50]
Example 2
- Input
- head = [7, 8], n = 2
- Output
- [8]
Constraints
- The list holds 1 to 5000 nodes.
- 1 ≤
n≤ the number of nodes. - Every value is between −10⁴ and 10⁴.
Show the pattern
Linked list
"n from the end" in a list you can only walk forwards: send one pointer n nodes ahead, then move both together, and the trailing one stops just before the node to remove.
See linked list in a visualiserShow the approach
Put a dummy node in front of the head and start two pointers, fast and slow, on it. Move
fast forward n nodes. Then move both one node at a time until fast is on the last node.
They stay n nodes apart, so slow is now just before the node to remove: skip it with
slow.next = slow.next.next.
Return dummy.next. It is the right head even when the old head was the node removed.
Time: O(n) · Space: O(1)