4.9.4 — Remove Nth Node From End of List

LeetCode 19 · Medium · ★ Blind 75

The problem

Remove the n-th node counting from the end, and return the head.

1 → 2 → 3 → 4 → 5,  n = 2   →   1 → 2 → 3 → 5
1,                  n = 1   →   (empty list)

n is always valid. The follow-up asks for one pass.

The Plain-English Breakdown

You are given a linked list. I want you to count backward from the very last node. When you reach the n-th node from the end, delete it from the list by bypassing it. Since you can't walk backward in a singly linked list, this is a puzzle about relative distancing.

Constraints to note:

• n is guaranteed to be valid (it will never ask for the 10th from the end if the list only has 3 nodes).
• The list length is up to 30. (This means even a two-pass O(N) solution is perfectly fast enough, the "one pass" requirement is purely to test your pointer mastery).

Brute Force Analysis (Two-Pass)

The obvious way is to do two passes.

1. Walk from head to null, counting how many nodes there are. Let's say length L.
2. The node to remove is at index L - n from the start.
3. Walk again from the start, stop one node before L - n, and change its next pointer to skip the target node.

• Why it's sub-optimal: It takes O(N) time and O(1) space, which is great! But it requires walking the list twice. If the list is a stream of data arriving over a network, you can't "rewind" to the beginning. The interviewer wants to see if you can do it without looking back.

The pattern

Counting from the end is awkward in a singly linked list, because you can only walk forwards. The two-pass answer is easy: count the length, then walk length - n steps and unlink. That is two passes.

The one-pass version uses a gap. Move one pointer n steps ahead, then advance both together. When the leading pointer reaches the end, the trailing one is exactly n from the end — because the distance between them never changes.

n = 2

1 → 2 → 3 → 4 → 5
↑       ↑
slow   fast        (gap of 2)

...both advance until fast falls off the end...

1 → 2 → 3 → 4 → 5
        ↑       ↑
       slow    fast(null)

To delete a node in a singly linked list you need the node before it, so the trailing pointer must stop one short of the target. That is arranged by starting it at a dummy head.

ELI5 Analogy: Imagine a measuring tape that is exactly n inches long. You place the front of the tape on the first node, and the back of the tape behind the start line. You slide the whole tape forward one node at a time. When the front of the tape hits the end of the list, the back of the tape is pointing exactly at the node you need to modify! The tape guarantees the fixed distance is maintained.

Code Walkthrough

1. The Dummy Node: We create a dummy node and point its next to head. This is our safety net, saving us from writing a special if statement for deleting the very first node.
2. Pointer Setup: Both slow (back of the tape) and fast (front of the tape) start at dummy.
3. Creating the Gap: We loop n times, advancing fast by one step each time. Now, fast is exactly n steps ahead of slow.
4. Sliding the Tape: We loop while fast.next is not null. We move both slow and fast forward one step at a time. We stop when fast is on the very last node of the list.
5. The Unlink: Because we stopped when fast was at the end, slow is sitting exactly one node before the target node. We simply write slow.next = slow.next.next to route the pointer around the target node, essentially deleting it.
6. Return: We return dummy.next (which is the true head of the list), safely handling cases where the original head was the node we deleted.

The solution

Python

class Solution:
    def removeNthFromEnd(self, head, n: int):
        dummy = ListNode(0, head)
        slow = fast = dummy

        for _ in range(n):              # open a gap of n
            fast = fast.next

        while fast.next:                # advance until fast is on the last node
            slow = slow.next
            fast = fast.next

        slow.next = slow.next.next      # unlink

        return dummy.next

TypeScript

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  const dummy = new ListNode(0, head);
  let slow = dummy, fast = dummy;

  for (let i = 0; i < n; i++) fast = fast.next!;

  while (fast.next) {
    slow = slow.next!;
    fast = fast.next;
  }

  slow.next = slow.next!.next;

  return dummy.next;
}

The dummy head is doing real work here, not just tidying. Consider 1, n = 1: the node to remove is the head itself, and there is no previous node to rewire. With a dummy in front, the head has a predecessor like everything else, and dummy.next becomes null — the correct empty list. Without it you need a separate branch for "remove the head".

Both pointers start at dummy, not at head. That is what makes slow land one node before the target rather than on it. If you start them at head, slow ends up on the node to delete and cannot unlink it.

while fast.next rather than while fast. You want fast to stop on the last node, not past it. Advancing one step further would leave slow one node too far along.

Trace

1 → 2 → 3 → 4 → 5, n = 2.

After the gap loop: slow at dummy, fast at node 2.

step	slow	fast
1	1	3
2	2	4
3	3	5

fast.next is null, so stop. slow is on node 3, and slow.next is node 4 — the second from the end. Unlink it: 3 → 5. ✓

Complexity

O(n) time, one pass. O(1) space.

The two-pass version has exactly the same complexity. The one-pass version is not asymptotically better; it matters when the data is a stream you can only read once, which is the real reason the follow-up exists.

Derivation:

• Time Complexity: O(N). We advance the fast pointer N times until it hits the end of the list. The slow pointer advances N-n times. Both move sequentially without nested loops, so the time scales linearly with the length of the list.
• Space Complexity: O(1). We allocate exactly one dummy node and two pointer variables (slow, fast). No arrays or recursive stacks are used, so memory usage is constant regardless of list size.

Edge cases

• Removing the head — handled by the dummy.
• A single-node list with n = 1 — dummy.next becomes null and the function returns an empty list.
• n equals the list length — the head is removed, same as above.

Try each of these mentally before you say you are done. They are where this problem's bugs live.

Where this goes next

The fixed-gap two pointers idea shows up whenever a problem is phrased relative to the end of a sequence:

• Middle of the Linked List — a gap of half, achieved by moving one pointer twice as fast.
• Linked List Cycle — the same two pointers with different speeds, which is 4.9.7.
• k-th from the end, in any streaming context — log tailing, sliding buffers.

The rule: to reach a position defined from the end in one pass, open a gap and move both pointers together.

What the interviewer will push on

"Why the dummy node?" So that removing the head needs no special case.

"Why do both pointers start at the dummy?" To leave slow one node before the target, since deletion needs the predecessor.

"What if n were larger than the list?" The problem promises it is not. In real code you would check, because the gap loop would dereference null.

"Do it in two passes." Count the length, then walk length - n from a dummy. Say it is the same complexity and only differs for streams.

One thing to volunteer: say what happens when the target is the head, before they ask. That is the edge case this problem is built around.

Next: 4.9.5 Copy List with Random Pointer — a deep copy where the pointers can go anywhere.