Remove the nth node from the end in one pass: start a fast runner n steps ahead, move both until it falls off, then unlink the next node.
▼The problem
LeetCode 19 (Medium). Given the head of a linked list, remove the nth node from the end of the list and return its head.
Examples (LeetCode's): head = [1,2,3,4,5], n = 2 → [1,2,3,5] (the walkthrough), [1], n = 1 → [] and [1,2], n = 1 → [1].
The solution
def removeNthFromEnd(head, n):
dummy = ListNode(0, head)
fast = slow = dummy
for _ in range(n + 1):
fast = fast.next
while fast:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummy.nextTranscript
Remove Nth Node From End of List. Given a linked list and a number n, remove the nth node from the end and return the head.
Take one through five with n equal to two. Second from the end is four, so we get one, two, three, five. One node with n of one leaves an empty list, and one, two with n of one leaves just one.
The simple way walks twice: count the length, five, then stop at node five minus two, right before the target, and skip it.
One pass is enough. Rope two pointers together at a dummy node before the head. Fast climbs n plus one steps ahead. Then both step together, keeping the gap, until fast falls off the end. Slow is right before the target. Unlike the tortoise and hare, they share one speed; only the gap is fixed.
In code, fast and slow start on the dummy. Move fast n plus one times. While fast isn't null, step both. Then slow dot next skips to slow dot next dot next. Return dummy dot next.
One to five, n is two. Fast climbs three: one, two, three. Together: slow one, fast four. Slow two, fast five. Slow three, fast falls off. Slow's next is four: skip it. One, two, three, five.
Why the dummy? With one node and n of one, slow never leaves the dummy, so it can remove the head itself.
One pass: order L time, order one space.
Rope up, walk to the edge, snip. That's Remove Nth Node From End of List.