Remove Nth Node From End of List

mediumLinked List20 stepsJava · Python · C++

Remove the n-th node from the end in one pass. Move fast n steps ahead of slow (both starting at a dummy node), then move both until fast is at the last node. slow is now just before the node to delete.

▶ Watch the animated trace

Traced input: head = [1, 2, 3, 4, 5], n = 2 → [1, 2, 3, 5]. Original problem: neetcode.io/problems/remove-node-from-end-of-linked-list

Complexity

BestO(L)

AverageO(L)

WorstO(L)

SpaceO(1)

One pass over the list of length L.

Key idea

Keep a gap of exactly n nodes between fast and slow.
When fast is on the last node, slow is right before the target.
A dummy head makes removing the first node work the same way.

Common mistakes

Without a dummy node, removing the head needs a special case.
Off-by-one in the gap: stopping slow on the target instead of before it.

Solution

Java

ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0, head), slow = dummy, fast = dummy;
    for (int i = 0; i < n; i++) {
        fast = fast.next;
    }
    while (fast.next != null) {
        slow = slow.next;
        fast = fast.next;
    }
    slow.next = slow.next.next;
    return dummy.next;
}

Python

def removeNthFromEnd(head: Optional[ListNode], n: int) -> Optional[ListNode]:
    dummy = ListNode(0, head)
    slow = fast = dummy
    for _ in range(n):
        fast = fast.next
    while fast.next:
        slow = slow.next
        fast = fast.next
    slow.next = slow.next.next
    return dummy.next

C++

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode dummy(0, head);
    ListNode *slow = &dummy, *fast = &dummy;
    for (int 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;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Remove the head slow stays on the dummy, so dummy.next is skipped.	`head = [1, 2], n = 2`	`[2]`
Only node The result is empty.	`head = [1], n = 1`	`[]`
Remove the tail slow ends on the second-to-last node.	`head = [1, 2, 3], n = 1`	`[1, 2]`