What is the brute force approach and complexity for Remove Nth Node From End of List?

Pass 1 counts L; pass 2 stops before index L − n and unlinks it with time complexity O(L) and space complexity O(1).

What is the optimal approach and complexity for Remove Nth Node From End of List?

Put fast n + 1 ahead of slow; when fast hits null, slow is just before the target with optimal time complexity O(L) and space complexity O(1).

How do you identify the pattern for Remove Nth Node From End of List?

Look for key signals in the prompt: "n-th from the end" indicates A position measured from null. A fixed gap between two pointers measures it in one pass.; "remove a node" indicates You need the node before it, so make the gap one bigger (n + 1).; "may remove the head" indicates Use a dummy node so the head also has a node before it.; "one pass" indicates No counting pass first. Let fast do the measuring..

Remove Nth Node From End of List

Medium·LeetCode #19Basic Anchor

LeetCode

Jump:

30-Second Mental ModelLinked List Fast & Slow — Gap / alignment (fixed gap n + 1 from a dummy)

Complexity:O(L)→O(L)

Key Insight

Put a dummy node before the head. Start slow and fast on the dummy and move fast ahead by n + 1 nodes. Now move both one step at a time. The gap never changes, so when fast becomes null, slow is n + 1 nodes before null, which is the node just before the n-th from the end. Unlink with slow->next = slow->next->next and return dummy.next.

Core Validity Invariant

The gap from slow to fast is always exactly n + 1 nodes, so when fast is null, slow is the node just before the n-th node from the end.

Problem

You are given the head of a singly linked list and a number n.

Delete the node that is n-th from the end of the list (the last node is 1st from the end), and return the head of the changed list.

Follow-up: can you do it in one pass over the list?

Input

The head of a linked list, and an integer n with 1 ≤ n ≤ the length of the list.

Output

The head of the list after that one node is removed. It may be a different node than before, or null if the list becomes empty.

Example 1

Input: head = [1, 2, 3, 4, 5], n = 2

Output: [1, 2, 3, 5]

Counting from the end: 5 is 1st, 4 is 2nd. So node 4 is removed.

Example 2

Input: head = [1], n = 1

Output: []

The only node is removed, so the list is empty.

Example 3

Input: head = [1, 2], n = 1

Output: [1]

The last node (2) is removed.

Constraints

• The list has `sz` nodes, 1 ≤ sz ≤ 30
• 0 ≤ Node.val ≤ 100
• 1 ≤ n ≤ sz

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
To delete a node in a singly linked list, which node do I actually need to be standing on?
2.
What is the n-th node from the end if I count from the front instead? What do I need to know for that?
3.
What happens if the node to delete is the head? Is there a node before it?
4.
If two pointers are exactly k nodes apart and the front one reaches the end, where is the back one?
5.
How far apart should they be so the back one stops one node before the target, not on it?

Brute force approach

Idea

First walk the whole list to count its length L. The n-th node from the end is then index L − n from the front. Walk again and stop on the node just before it, then skip over it. If L − n is 0, the head itself goes, so return head->next.

Thinking process

1
"From the end" is hard in a list that only goes forwards. "From the front" is easy.
2
If I knew the length L, the n-th from the end would be index L − n from the front.
3
So count first, then walk to the node before index L − n and change its next pointer.
4
The head has no node before it, so removing it needs its own if.

Code & Implementation

brute.cpp

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // Pass 1: count the nodes.
        int len = 0;
        for (ListNode* cur = head; cur != nullptr; cur = cur->next) len++;

        // n-th from the end = index len - n from the front (0-based).
        int target = len - n;
        if (target == 0) return head->next;   // removing the head: the 2nd node is the new head

        // Pass 2: stop on the node just BEFORE the target, then skip over it.
        ListNode* prev = head;
        for (int i = 0; i < target - 1; i++) prev = prev->next;
        prev->next = prev->next->next;
        return head;
    }
};

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // Pass 1: count the nodes.
        int len = 0;
        for (ListNode cur = head; cur != null; cur = cur.next) len++;

        // n-th from the end = index len - n from the front (0-based).
        int target = len - n;
        if (target == 0) return head.next; // removing the head: the 2nd node is the new head

        // Pass 2: stop on the node just BEFORE the target, then skip over it.
        ListNode prev = head;
        for (int i = 0; i < target - 1; i++) prev = prev.next;
        prev.next = prev.next.next;
        return head;
    }
}

from typing import Optional, List, Dict, Set, Tuple

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        # Pass 1: count the nodes.
        length = 0
        cur = head
        while cur is not None:
            length += 1
            cur = cur.next

        # n-th from the end = index length - n from the front (0-based).
        target = length - n
        if target == 0:
            return head.next if head else None  # removing the head: the 2nd node is the new head

        # Pass 2: stop on the node just BEFORE the target, then skip over it.
        prev = head
        for _ in range(target - 1):
            prev = prev.next

        if prev and prev.next:
            prev.next = prev.next.next

        return head

export class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = (val === undefined ? 0 : val);
        this.next = (next === undefined ? null : next);
    }
}

export function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
    // Pass 1: count the nodes.
    let len = 0;
    for (let cur = head; cur !== null; cur = cur.next) len++;

    // n-th from the end = index len - n from the front (0-based).
    const target = len - n;
    if (target === 0) return head ? head.next : null; // removing the head: the 2nd node is the new head

    // Pass 2: stop on the node just BEFORE the target, then skip over it.
    let prev = head!;
    for (let i = 0; i < target - 1; i++) prev = prev.next!;
    prev.next = prev.next!.next;
    return head;
}

Complexity

Time O(L)Space O(1)

It is already linear, but it reads the list twice: about L + (L − n) steps. The follow-up asks for one pass, and the special case for the head is easy to forget.

Optimized approach

Idea

Start from brute force

Brute force walks the whole list once only to learn L, then walks again to reach index L − n − 1.

Find the repeated work

The first pass is used only to measure the distance to the end. The second pass then walks the same nodes again. A second pointer running ahead can measure that distance while we walk.

Define the state — what variables do I need?

dummy: A node placed before the head, so every real node (even the head) has a node before it.
fast: The front pointer. It starts n + 1 nodes ahead of slow and walks until it becomes null.
slow: The back pointer. It is always exactly n + 1 nodes behind fast.

Define validity

The gap from slow to fast is always exactly n + 1 nodes, so when fast is null, slow is the node just before the n-th node from the end.

Define the transitions — when does each pointer move, and why is it safe?

Before the loop

slow = fast = &dummy; move fast n + 1 times

This sets the gap. n ≤ L, so fast takes at most L + 1 steps from the dummy and lands on a node or exactly on null, never past it.

While fast != null

fast = fast->next; slow = slow->next

Both move one step, so the gap stays n + 1. We stop the moment fast is null, which is the end of the list.

After the loop

slow->next = slow->next->next; return dummy.next

slow->next is the target. Skipping over it removes it. If the head was removed, dummy.next is now the new head, so always return dummy.next, not head.

What does the current window add to the answer?

The single node slow->next is the answer to "which node goes". One pointer change removes it.

Code & Implementation

optimal.cpp

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // The dummy sits before the head, so even the head has a node before it.
        ListNode dummy(0, head);
        ListNode* slow = &dummy;
        ListNode* fast = &dummy;

        // Give fast a head start of n + 1 nodes.
        for (int i = 0; i <= n; i++) fast = fast->next;

        // Move both until fast falls off the end. The gap stays n + 1,
        // so slow stops on the node just BEFORE the n-th from the end.
        while (fast != nullptr) {
            fast = fast->next;
            slow = slow->next;
        }

        slow->next = slow->next->next;   // unlink the n-th node from the end
        return dummy.next;               // the head may have changed
    }
};

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // The dummy sits before the head, so even the head has a node before it.
        ListNode dummy = new ListNode(0, head);
        ListNode slow = dummy;
        ListNode fast = dummy;

        // Give fast a head start of n + 1 nodes.
        for (int i = 0; i <= n; i++) fast = fast.next;

        // Move both until fast falls off the end. The gap stays n + 1,
        // so slow stops on the node just BEFORE the n-th from the end.
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        slow.next = slow.next.next; // unlink the n-th node from the end
        return dummy.next;          // the head may have changed
    }
}

from typing import Optional, List, Dict, Set, Tuple

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        # The dummy sits before the head, so even the head has a node before it.
        dummy = ListNode(0, head)
        slow = dummy
        fast: Optional[ListNode] = dummy

        # Give fast a head start of n + 1 nodes.
        for _ in range(n + 1):
            if fast:
                fast = fast.next

        # Move both until fast falls off the end. The gap stays n + 1,
        # so slow stops on the node just BEFORE the n-th from the end.
        while fast is not None:
            fast = fast.next
            if slow.next:
                slow = slow.next

        if slow.next:
            slow.next = slow.next.next  # unlink the n-th node from the end

        return dummy.next  # the head may have changed

export class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = (val === undefined ? 0 : val);
        this.next = (next === undefined ? null : next);
    }
}

export function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
    // The dummy sits before the head, so even the head has a node before it.
    const dummy = new ListNode(0, head);
    let slow: ListNode = dummy;
    let fast: ListNode | null = dummy;

    // Give fast a head start of n + 1 nodes.
    for (let i = 0; i <= n; i++) fast = fast!.next;

    // Move both until fast falls off the end. The gap stays n + 1,
    // so slow stops on the node just BEFORE the n-th from the end.
    while (fast !== null) {
        fast = fast.next;
        slow = slow.next!;
    }

    slow.next = slow.next!.next; // unlink the n-th node from the end
    return dummy.next;           // the head may have changed
}

Complexity

Time O(L)Space O(1)

One pass: fast walks to null once and slow trails behind it. The dummy is a local variable, so no extra memory to free.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Pass 1 counts L; pass 2 stops before index L − n and unlinks it	O(L)	O(1)
Optimal	Put fast n + 1 ahead of slow; when fast hits null, slow is just before the target	O(L)	O(1)

Why does this belong to this pattern?

Clues in the problem statement

“n-th from the end”A position measured from null. A fixed gap between two pointers measures it in one pass.
“remove a node”You need the node before it, so make the gap one bigger (n + 1).
“may remove the head”Use a dummy node so the head also has a node before it.
“one pass”No counting pass first. Let fast do the measuring.

singly linked list+position counted from the end+fixed gap between two pointers→Linked List Fast & Slow — Gap / alignment (fixed gap n + 1 from a dummy)

This is the anchor of the gap idea. In cycle and middle problems, fast moves faster than slow. Here both move at the same speed, and fast just starts earlier. The head start (n + 1) is chosen so that when fast reaches the end, slow is exactly where we need it. The next two questions reuse this: Intersection uses a head start equal to the length difference, and Swapping Nodes uses a gap of k − 1 to find the k-th from the end.

Don't make this mistake

No dummy node, so removing the head crashes

✗ ListNode* slow = head; ListNode* fast = head; for (int i = 0; i < n; i++) fast = fast->next; while (fast->next) { ... } // fast is null when n == length

✓ ListNode dummy(0, head); ListNode* slow = &dummy; ListNode* fast = &dummy; for (int i = 0; i <= n; i++) fast = fast->next;

When n equals the length, the node to remove is the head and there is no node before it. Without a dummy, fast becomes null after the head start and fast->next crashes. With a dummy, the dummy is the node before the head and the same code works.

Gap of n instead of n + 1

✗ for (int i = 0; i < n; i++) fast = fast->next; // gap n while (fast) { fast = fast->next; slow = slow->next; } slow->next = slow->next->next;

✓ for (int i = 0; i <= n; i++) fast = fast->next; // gap n + 1

With a gap of n, slow lands on the n-th node from the end, not before it. Then slow->next = slow->next->next deletes the node after the target. On [1, 2, 3, 4, 5], n = 2 you'd remove 5 instead of 4.

Returning head instead of dummy.next

✗ slow->next = slow->next->next; return head;

✓ return dummy.next;

If the head was removed, head still points at the removed node. dummy.next always points at the real first node of the new list.

Thinking fast must move twice as fast

This is the pattern-confusion trap: in cycle and middle questions fast moves 2 steps per turn. Here the speed is the same (1 and 1); only the start differs. If fast moved 2 steps, the gap would keep growing and slow would stop near the middle, not near the end.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Linked List — Fast & Slow translate into production architectures and low-level memory mechanics.

LLD Architecture