Remove Nth Node From End

"The n-th from the end" is easy on an array: it is index length − n. A linked list does not know its length, and it cannot walk backwards. So the obvious solution takes two passes — one to count, one to walk. Interviewers ask for one pass, and the trick they want is a small, reusable idea: two pointers a fixed distance apart.

The problem also needs the dummy head. When n equals the length, the node to remove is the head itself, which has no predecessor. Without a dummy, that case needs its own branch.

The problem

You are given the head of a list and an integer n. Remove the n-th node counting from the end (n = 1 is the last node) and return the head of the resulting list.

• 1 → 2 → 3 → 4 → 5, n = 2 → 1 → 2 → 3 → 5. The 2nd node from the end is 4.
• 10 → 20, n = 2 → 20. The node to remove is the head.
• 9, n = 1 → an empty list.

Constraints: 1 to 10⁴ nodes, and 1 ≤ n ≤ length.

Clarifying questions

• Is n always valid? Assume 1 ≤ n ≤ length. If not, ask what to return — usually the list unchanged.
• Does n = 1 mean the last node? Yes.
• One pass required? That is the usual follow-up; plan for it.

Approach 1: count, then walk

Walk once to count the nodes. The target is at position length − n from the front (counting from 0), so its predecessor is length − n steps from a dummy node.

1def remove_nth_from_end_two_pass(head: ListNode | None, n: int) -> ListNode | None:2    """Count the nodes, then walk to the one before the target."""3    length = 04    node = head5    while node is not None:6        length += 17        node = node.next8    dummy = ListNode(0, head)9    previous = dummy10    for _ in range(length - n):          # stop on the node before the target11        previous = previous.next12    previous.next = previous.next.next13    return dummy.next

Time: O(L) for L nodes. Space: O(1).

Be honest about this one: it is already optimal in big-O terms. Two passes of L steps is still O(L). The reason to improve it is the requirement, not the speed: the interviewer asks for one pass, and a one-pass method also works when you can read the list only once (a stream). Another brute force stores every node in an array and indexes nodes[L − n − 1]: one pass, but O(L) extra space.

The key insight

Keep two pointers, lead and trail, with lead exactly n nodes ahead. Move them forward together, one step each. The gap never changes. So when lead stands on the last node, trail stands exactly n nodes behind it — which is the node just before the n-th from the end.

Two details make it land on the predecessor, every time:

• The loop stops when lead is on the last node (lead.next is None), not when lead falls off the end (lead is None). The last node is 1st from the end, so the node n behind it is (n + 1)-th from the end — the predecessor of the target. Run one step further and trail lands on the target instead.
• Both pointers start at the dummy, not at the head. When the target is the head itself (n equals the length), its predecessor is "position −1", and only the dummy can stand there. Starting at the head, opening the gap would walk lead off the end of the list.

With both, trail.next is the node to remove, and trail.next = trail.next.next removes it — even when it is the real head, because then trail is still the dummy.

Approach 2: one pass with a fixed gap

1def remove_nth_from_end(head: ListNode | None, n: int) -> ListNode | None:2    """One pass: hold a gap of n nodes between lead and trail."""3    dummy = ListNode(0, head)4    lead = trail = dummy5    for _ in range(n):                   # open the gap6        lead = lead.next7    while lead.next is not None:         # stop when lead is on the LAST node8        lead = lead.next9        trail = trail.next10    trail.next = trail.next.next         # trail is just before the target11    return dummy.next

Dry run on 1 → 2 → 3 → 4 → 5, n = 2:

trail is node 3 and trail.next is node 4, the 2nd from the end. Removing it gives 1 → 2 → 3 → 5.

Dry run on 10 → 20, n = 2 — the head case:

trail is the dummy, so dummy.next = dummy.next.next skips node 10, and the function returns dummy.next, which is node 20. The head was removed with no special case.

Time: O(L) — lead walks the list once and trail follows. Space: O(1).

Strictly, the two pointers together take about 2L steps, the same as the two-pass version. "One pass" means the list is read in a single sweep from front to back: once lead has passed a node, nothing ever needs to reach it from the head again. That is what makes the idea useful beyond this problem — it works whenever you can walk forward only once.

Edge cases

• Removing the head (n = length): trail never leaves the dummy, and the dummy's next is rewired. Shown in the second dry run.
• A one-node list: 9, n = 1: the gap puts lead on 9, the loop does not run, and dummy.next becomes None. Returns an empty list.
• Removing the last node (n = 1): trail stops on the second-to-last node and its next becomes None.
• n larger than the length (if allowed): opening the gap would step past the end. Check for None inside the gap loop and return the list unchanged.

Follow-ups

• Return the n-th node from the end without removing it: same gap, but start both at the head and stop when lead is None; then trail is the node itself.
• Rotate the list right by k: find the length, take k % length, use the same gap idea to find the new tail (the (k+1)-th from the end), then cut and reattach the old tail to the old head.
• Delete the middle node: a different pointer trick — slow and fast at different speeds rather than a fixed gap. See Fast and Slow Pointers.