Remove Nth Node From End of List
Given the head of a linked list, remove the nth node from the end of the list and return its head.
- The number of nodes in the list is sz.
- 1 <= sz <= 30
- 0 <= Node.val <= 100
- 1 <= n <= sz
head = [1,2,3,4,5], n = 2[1,2,3,5]head = [1], n = 1[]head = [1,2], n = 2[2]We must delete the node that sits N places from the end of a singly linked list and return the head. The trouble is that "from the end" fights against how a linked list works: you can only move forward from the head, you can't look backward, and you don't know the length until you've walked all the way to the tail. Counting from the front is easy; the question asks us to count from the back.
Walk once to count the nodes — say there are 5. The N-th node from the end is the (5 − N)-th from the front, so its predecessor (the node we must rewire) is one before that. Walk a second time to that predecessor and splice the target out by pointing around it.
length = 0
curr = head
while curr: # first pass: measure
length += 1
curr = curr.next
curr = head
for _ in range(length - n - 1): # second pass: walk to the predecessor
curr = curr.next
curr.next = curr.next.next # skip over the targetCorrect, but it walks the list twice, and it's fiddly when the target is the head itself (there's no predecessor to rewire). Both problems disappear with the right two-pointer trick.
Here's the fixed-gap shape of the family. Instead of matching speeds, we lock in a distance. Send one pointer — the front runner — ahead by N steps first, while the other waits at the start. Now they are exactly N apart. From this moment, move both forward at the same speed, one step each. The gap never changes: it stays N the whole way. So the instant the front runner reaches the end of the list, the back pointer is sitting exactly N nodes from the end — right on top of the node we care about. We converted "N from the end" (which needs the length) into "keep a gap of N and walk to the end" (which doesn't). One pass, no counting.
To delete a node we actually need its predecessor, so we want the back pointer to stop one node before the target, not on it — that means starting the gap at N+1. But there's a snag: if the target is the very first node, its predecessor is nothing at all, and there's nowhere to stand. The clean fix is a dummy node: a throwaway node glued in front of the real head, pointing at it. Start both pointers on the dummy. Now every real node — including the original head — has a node in front of it to rewire, so deleting the head stops being a special case. At the end we return dummy.next, which is the head of whatever list remains.
dummy = Node(0, head)
lead = dummy
trail = dummy
for _ in range(n + 1): # open a gap of N+1 between them
lead = lead.next
while lead: # walk both until the front runner falls off
lead = lead.next
trail = trail.next
trail.next = trail.next.next # trail is right before the target — splice it out
return dummy.nexttrail land on the predecessor rather than on the target itself — try it with N=1 on a short list and you'll see that a gap of only N leaves trail sitting on the doomed node with no way to unlink it. The dummy node earns its keep in exactly the case where the target is the head: trail stays on the dummy, dummy.next = dummy.next.next drops the old head, and dummy.next returns the new one — no branch needed.lead and trail on the dummy. Open the gap: move lead forward n+1 = 3 steps → dummy → 1 → 2 → 3. Now lead is on node 3.lead falls off: lead 3→4 (trail dummy→1), lead 4→5 (trail 1→2), lead 5→null (trail 2→3). Stop.trail is on node 3, exactly before the target. Splice: node 3's next skips node 4 to node 5. List becomes [1, 2, 3, 5].This is the third face of same-direction two pointers you've now seen: not a speed ratio like the middle and cycle problems, but a constant offset. The reflex to build: any time a problem measures something "from the end" of a forward-only structure, ask whether a lead pointer set that many steps ahead can turn it into an ordinary walk to the end.
N-th Node Coordinate Mapping
Operation Status
The Silent End
We want to remove the N-th node from the end. But in a singly linked list, we can't see the finish line until we cross it. How do we target the unseen?
When the Fast pointer is N steps ahead, it "drags" the Slow pointer exactly N nodes behind it. Hits the end, found the target.
To handle edge cases (like removing the head), always start with a **Dummy** node pointing to the head.