The problem
Given the head of a linked list, remove the n-th node counting from the end (the last node is the 1st from the end), and return the head.
Examples
01
- Input
head = [1, 2, 3, 4, 5], n = 2
- Output
[1, 2, 3, 5]
02
- Input
head = [1], n = 1
- Output
[]
03
- Input
head = [1, 2], n = 1
- Output
[1]
Constraints
- 1 ≤ number of nodes ≤ 30
- 0 ≤ Node.val ≤ 100
- 1 ≤ n ≤ number of nodes
The idea
Counting the list first and then walking again takes two passes. Instead, keep two pointers exactly n + 1 nodes apart: when the front one runs off the end, the back one stands just before the node to remove.
Both start on a dummy node placed before the head, so removing the head itself is not a special case. Move the front one n + 1 steps, then both together until the front one is past the end; then skip the next node with slow.next = slow.next.next.
- Time
- O(n) — one pass
- Space
- O(1)
Solution · every language run against every case
class Solution: def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]: dummy = ListNode(0, head) # so removing the head needs no special case lead = trail = dummy for _ in range(n + 1): lead = lead.next # put lead n + 1 nodes ahead of trail while lead: lead, trail = lead.next, trail.next trail.next = trail.next.next # trail sits just before the node to remove return dummy.next