LeetCode 19 – Remove Nth Node From End of List

You cannot walk a singly linked list backwards, so "the nth node from the end" has to be found from the front. The obvious way is to measure the list, then walk length - n nodes. The follow-up asks for one pass, and the answer is a pair of pointers held a fixed distance apart.

The problem

Remove the nth node from the end of a linked list and return the head. n is guaranteed valid — at least 1 and no more than the length.

Input:  1 -> 2 -> 3 -> 4 -> 5,  n = 2
Output: 1 -> 2 -> 3 -> 5          the 4 is removed

Input:  1,                       n = 1
Output: (empty list)             removing the only node

Input:  1 -> 2,                  n = 2
Output: 2                        removing the head

The idea: a gap of a fixed width

Start two pointers at the front and move fast ahead by n nodes, then advance both together. When fast falls off the end, slow has travelled exactly length - n nodes — it is sitting on the node to delete. The gap between them never changes, so the position "n from the end" is found without ever knowing the length.

Except sitting on the target is not useful. To unlink a node from a singly linked list you need the node before it, so open the gap one wider — n + 1 — and slow lands on the predecessor instead.

n = 2, so the gap is 3

dummy  1  2  3  4  5  null
  ↑          ↑
slow        fast          ← after opening the gap

dummy  1  2  3  4  5  null
             ↑          ↑
           slow        fast   ← both advanced until fast fell off

slow is the 3; slow.next is the 4; unlink it.

Why the dummy node is not optional here

"The node before the target" does not exist when the target is the head — and n == length is exactly that case. Without a dummy you need a separate branch that returns head.next, and forgetting it is the single most common way to fail this problem.

Starting both pointers at a dummy node whose next is the head gives the head a predecessor like every other node, and the branch disappears. It also makes the return value correct for free: dummy.next is the new head whether or not the old one survived, and it is null when the list had one node and that node was removed.

Java

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);   // gives the head a predecessor
        ListNode fast = dummy, slow = dummy;

        // Open a gap of n + 1, so slow stops on the node BEFORE the target.
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }

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

        slow.next = slow.next.next;   // unlink
        return dummy.next;            // null if the list is now empty
    }
}

i <= n rather than i < n is the whole "one wider" adjustment, and it is the line to double-check on the whiteboard. Trace it on 1 -> 2 -> 3 -> 4 -> 5 with n = 2: fast makes three hops to the 3, both pointers then advance twice, fast becomes null and slow is on the 3 — the node before the 4. Correct.

Python

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

        for _ in range(n + 1):        # gap of n + 1
            fast = fast.next

        while fast:
            fast = fast.next
            slow = slow.next

        slow.next = slow.next.next
        return dummy.next

Complexity

O(L) time and O(1) space, in a single pass. The two-pass version — count the length, then walk L - n — is the same asymptotic cost and is a perfectly good first answer. Say it, then say the one-pass version exists and write that; the interviewer is going to ask for it anyway.

"One pass" is worth a moment of honesty: the pointers together still traverse about L + n nodes, so it is not less work than counting. What it buys is not needing the list to be traversable twice — which matters when the input is a stream you can only read once.

What the interviewer is checking

• That you use a dummy head instead of special-casing removal of the first node.
• That the gap is n + 1, not n, and that you can say why.
• n == length — removing the head. This is the case that breaks naive solutions.
• A single-node list with n = 1, which must return an empty list rather than throwing.
• That you offer the two-pass version first and then improve it, rather than going quiet while you work out the pointer arithmetic.