#19MediumLinked lists

Remove Nth Node From End of List

The tell: Positional removal counted from the tail, in one pass.

How you get there

1Advance a lead pointer n steps ahead of a trailing one.
2Move both until the lead reaches the end; the trail is then just before the target.
3A dummy head makes removing the first node identical to any other.

Solution

Python

def remove_nth_from_end(head, n: int):
    dummy = ListNode(0, head)
    lead = trail = dummy
    for _ in range(n):
        lead = lead.next
    while lead.next:
        lead = lead.next
        trail = trail.next
    trail.next = trail.next.next
    return dummy.next

Time: O(n)
Space: O(1)

What goes wrong

Without the dummy, deleting the head requires a separate branch that is easy to get wrong.

Test yourself on DSA Next: Merge Two Sorted Lists →