Count from the back
Remove the n-th node from the end in one walk by keeping two pointers a fixed distance apart. About 14 minutes.
A gap that stays the same
To remove the third node from the end of a chain you don't know the length of, put two fingers on the chain. Move the front finger forward three nodes first. Then move both fingers together, one node per step.
The gap between them stays three nodes the whole way. When the front finger is on the last node, the back finger is three nodes behind it. That is exactly the position you want, one step before the node to remove.
dummy = ListNode(0, head)
fast = slow = dummy
for _ in range(n):
fast = fast.nextBoth pointers start at the dummy in front of node 1 (shown at node 1 here). First move fast 2 nodes ahead.
Start on the dummy
To remove a node you must stand on the node before it. Start both fingers on a dummy node placed before the head. After the head start, move both until the front finger's next is nothing, meaning the front is on the last node.
Now the back finger is on the node just before the one to remove, whichever it is, even the head. Set its next to skip the next node, and return the dummy's next.
while fast.next:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummy.nextWhy start both pointers on a dummy node before the head?
- ASo the same steps work even if the node to remove is the head
- BIt makes the walk faster
- CTo count the nodes
Show the answer
So the same steps work even if the node to remove is the head. The back pointer can then stand before the head.
Remove from the back
Given the head of a singly linked list and a number n (1 ≤ n ≤ number of nodes), remove the n-th node from the end of the list (n = 1 is the last node) and return the head. Do it in one pass over the list.
head = [1, 2, 3, 4, 5], n = 2 → [1, 2, 3, 5]
1 ≤ number of nodes ≤ 5,000 · 1 ≤ n ≤ number of nodes