Free lesson · DSA Mastery - Interview Prep, End to End

Remove Nth Node From End of List

Medium7 min readdsalinked-list

Remove Nth Node From End of List

Remove Nth Node From End of List introduces the two-pointer gap technique - the answer to a recurring puzzle: how do you find a position counted from the end of a forward-only list in a single pass? The trick is to open a gap of exactly n nodes between two pointers, then advance both together; when the leader reaches the end, the trailer sits exactly n from the end. We climb three approaches: a two-pass solution (compute length, then walk to the node), the optimal one-pass two-pointer gap, and a recursive count-on-return-trip variant.

The dummy head reappears here for a crucial reason: the node to remove might be the head itself (removing the nth-from-end of an n-length list), and a dummy gives even the head a predecessor to rewire.

The Problem

Given the head of a linked list, remove the n-th node from the end of the list and return its head.

Example 1:

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

Explanation: The 2nd node from the end is 4; removing it yields 1->2->3->5.

Example 2:

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

Example 3:

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

Explanation: Removing the 2nd-from-end (the head) yields [2].

Constraints:

• The number of nodes is sz, with 1 <= sz <= 30.
• 1 <= n <= sz

Follow-up: Could you do this in one pass?

Approaches Overview

All are O(n) time. The two-pointer gap is the textbook answer because it satisfies the explicit one-pass follow-up with O(1) space.

Approach 1: Two-Pass

The Idea

First pass: count the list's length L. The node to remove is at position L - n from the front (0-indexed), so its predecessor is at position L - n - 1. Second pass: walk a dummy-anchored pointer that many steps and splice out the target. The dummy handles the case where the head itself is removed (L - n - 1 = -1 lands on the dummy).

Logic Flowchart

graph TD
    A["L = length(head)"] --> B["dummy -> head; pred = dummy"]
    B --> C["walk pred (L - n) steps"]
    C --> D["pred.next = pred.next.next"]
    D --> E["Return dummy.next"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style D fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the two-pass approach. We measure the length, then from a dummy before the head we walk length minus n steps to reach the target's predecessor, splice out the target, and return the dummy's next.

Code

public static ListNode removeNthFromEndTwoPass(ListNode head, int n) {
    int L = 0;
    for (ListNode p = head; p != null; p = p.next) L++;

    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode pred = dummy;
    for (int i = 0; i < L - n; i++) pred = pred.next;   // to predecessor
    pred.next = pred.next.next;                          // splice out target
    return dummy.next;
}

This Java code measures the length, then walks from a dummy before the head to the predecessor of the target - length minus n steps - and splices out the target node, returning the dummy's next.

Complexity

Time: O(n) - two passes. Space: O(1).

Correct and simple, but it traverses the list twice. The gap technique does it in one.

Approach 2: One-Pass Two-Pointer Gap - Optimal

The Idea

Anchor a fast and slow pointer at a dummy before the head. Advance fast by n + 1 steps, opening a gap of n + 1 nodes (so slow ends up at the target's predecessor). Then move both together until fast reaches null. Now slow.next is the node to remove - splice it out. The +1 in the gap is what positions slow at the predecessor rather than the target itself, enabling the rewire.

Logic Flowchart

graph TD
    A["dummy -> head; fast = slow = dummy"] --> B["advance fast by n+1 steps"]
    B --> C{"fast != null?"}
    C -->|Yes| D["fast = fast.next; slow = slow.next"]
    D --> C
    C -->|No| E["slow.next = slow.next.next (remove target)"]
    E --> F["Return dummy.next"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style D fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style E fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style F fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the one-pass gap. From a dummy, we advance the fast pointer n plus one steps to open a gap, then move both pointers together until fast reaches null. At that point slow sits at the target's predecessor, so we splice out slow's next.

Code

public static ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode fast = dummy, slow = dummy;

    for (int i = 0; i < n + 1; i++) fast = fast.next;   // gap of n+1
    while (fast != null) {                               // move together
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next;                          // slow is the predecessor
    return dummy.next;
}

// Usage:
// removeNthFromEnd([1,2,3,4,5], 2) -> [1,2,3,5]
// removeNthFromEnd([1], 1)         -> []

This Java code anchors fast and slow at a dummy, advances fast by n plus one to open the gap, then moves both until fast is null. Slow then rests at the target's predecessor, and splicing out slow's next removes the nth node from the end.

Step-by-Step Walkthrough

A frame-by-frame trace on [1, 2, 3, 4, 5], n = 2:

graph LR
    F0["fast,slow at dummy<br/>advance fast 3 steps<br/>fast at node 3"]
    F1["move together<br/>fast→4, slow→1"]
    F2["fast→5, slow→2"]
    F3["fast→null, slow→3<br/>(predecessor of 4)"]
    F4["slow.next = 5<br/>removes 4 → 1,2,3,5"]
    F0 --> F1 --> F2 --> F3 --> F4

    style F0 fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style F1 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F2 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F3 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F4 fill:#dc2626,stroke:#ef4444,color:#f1f5f9

This walkthrough removes the second-from-end of one through five. Fast advances three steps to node three, opening the gap. Moving both together, fast reaches null while slow rests at node three, the predecessor of four. Splicing out four gives one, two, three, five.

Result: [1, 2, 3, 5].

Complexity

Time: O(n) - single pass. Space: O(1).

Approach 3: Recursive Count on Return

The Idea

Recurse to the end of the list; on the way back up, count nodes from the end. When the return count equals n, the current node's caller holds the predecessor - link it past the target. Elegant (the count emerges naturally on the unwind) but uses O(n) stack.

Logic Flowchart

graph TD
    A["recurse(node) returns count-from-end"] --> B{"node == null?"}
    B -->|Yes| C["return 0"]
    B -->|No| D["count = recurse(node.next) + 1"]
    D --> E{"count == n + 1?"}
    E -->|Yes| F["node.next = node.next.next (skip target)"]
    E -->|No| G["no change"]
    F --> H["return count"]
    G --> H

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style E fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style F fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style G fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style H fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the recursive approach. We recurse to the end, then count nodes from the end on the way back. When the count reaching a node equals n plus one, that node is the predecessor, so we splice out its next. A dummy head handles removing the first node.

Code

public static ListNode removeNthFromEndRecursive(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    countFromEnd(dummy, n);
    return dummy.next;
}

private static int countFromEnd(ListNode node, int n) {
    if (node == null) return 0;
    int count = countFromEnd(node.next, n) + 1;
    if (count == n + 1) node.next = node.next.next;   // node is predecessor
    return count;
}

This Java code recurses to the end from a dummy, counting nodes from the end on the unwind. When a node's count from the end is n plus one, it is the predecessor of the target, so its next is spliced out.

Complexity

Time: O(n). Space: O(n) stack.

Complexity Comparison

All O(n) time. The two-pointer gap is the canonical answer - it satisfies the one-pass follow-up in O(1) space and teaches the reusable "fixed gap between pointers" idea. The dummy head is essential in all three to handle removing the head.

Variations & Follow-ups

Why advance fast by n + 1 and not n?

A gap of n + 1 (from the dummy) leaves slow at the target's predecessor when fast hits null, which is what you need to rewire slow.next. A gap of n would land slow on the target, with no handle to its predecessor.

Why is the dummy head essential here?

When the head itself is the nth-from-end (e.g. Example 3), its predecessor is the dummy. Without the dummy, removing the head needs a special branch.

How does this generalize?

The "fixed gap between two pointers, advance together" pattern solves any "kth from the end" query in one pass - finding it, removing it, or returning it.

What about edge cases?

• Remove the head (n == length): the dummy is slow's final position (Example 3).
• Single node, n = 1: Returns empty (Example 2).
• Remove the tail (n == 1): slow lands on the second-to-last node.
• n exceeds length: Excluded by constraints (1 <= n <= sz).

Common Interview Pitfalls

• Gap of n instead of n + 1. Lands slow on the target, not its predecessor.
• Omitting the dummy. Breaks head removal.
• Off-by-one in the advance loop. Verify on a 2-node list with n=2 (remove head).
• Dereferencing null when over-advancing fast. With valid n ≤ length, the n+1 advance stays in bounds (ending exactly at null when removing the head).

Why This Problem Matters

Remove Nth Node From End introduces the two-pointer gap - a fixed-distance offset between pointers that converts a "from the end" query into a single forward pass. This is one of the most reused linked-list patterns, underlying middle-finding, cycle problems, and any positional query on a forward-only list. Paired with the dummy head, it handles every edge case without special branches.

The next topic, Remove Duplicates from Sorted List II, raises the stakes on removal: instead of keeping one copy of each value, it deletes every node that has a duplicate - which means the head itself can be removed, making the dummy head indispensable and the predecessor-tracking more delicate.

Back to DSA Mastery - Interview Prep, End to End