LeetCode #19 — Medium

Remove Nth Node
From End of List

A complete visual walkthrough of the two-pointer technique for linked list problems — from brute force to a single elegant pass.

Solve on LeetCode

The Problem

Problem Statement

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]

Example 2:

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

Example 3:

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

Constraints:

The number of nodes in the list is sz.
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

Follow up: Could you do this in one pass?

Roadmap

Brute Force — Two Passes
The Core Insight — Two Pointers, One Pass
Algorithm Walkthrough
Edge Cases
Full Annotated Java Code
Interactive Demo
Complexity Analysis

Step 01

Brute Force — Two Passes

The most straightforward approach: first pass to count the total length L, then a second pass to find and remove the (L - n)th node.

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

Pass 1: Walk the entire list to count L = 5 nodes.

Pass 2: Advance to node L - n = 3 (the one before the target). Rewire its next pointer to skip node 4.

3 stop

Result: [1, 2, 3, 5]

This works and runs in O(L) time, but it requires two passes over the list. Can we do it in a single pass?

💡

The challenge: To remove the nth node from the end, we need to know how far the end is. But in a singly linked list, we cannot look backward. The two-pointer technique gives us a way to measure "distance from the end" in one pass.

Step 02

The Core Insight — Two Pointers, One Pass

Place two pointers, fast and slow, at the head. Advance fast by n steps first, creating a fixed gap. Then move both pointers together. When fast reaches the end, slow is exactly at the node before the target.

The Gap Trick

A dummy head node before the real head simplifies edge cases (like removing the first node). Both pointers start at the dummy.

After advancing fast by n+1 = 3 steps:

D slow

3 fast

← n+1 = 3 steps gap →

After moving both until fast == null:

3 slow

4 remove

null ← fast

⚡

Why does this work? The gap between fast and slow stays constant at n+1. When fast is at null (one past the last node), slow is n+1 positions behind — which is exactly the node before the nth-from-end node. This lets us rewire slow.next to skip the target.

Step 03

Algorithm Walkthrough

Let's trace through head = [1,2,3,4,5], n = 2 step by step.

Phase 1 — Setup

Create a dummy node pointing to head. Set both slow and fast to the dummy.

D slow fast

Phase 2 — Advance fast by n+1 = 3 steps

Move fast forward 3 times: D → 1 → 2 → 3. Now there is a gap of 3 nodes between the pointers.

D slow

3 fast

Phase 3 — Advance both until fast == null

Move both pointers one step at a time. The gap stays fixed.

          fast 3→4, slow D→1  | 
          fast 4→5, slow 1→2  | 
          fast 5→null, slow 2→3
        

3 slow

nullfast

Phase 4 — Delete the target

Set slow.next = slow.next.next. Node 3 now points directly to node 5, skipping node 4.

3.next = 5 (skipped 4)

Result

Return dummy.next which is the (possibly new) head of the list.

Step 04

Edge Cases

The dummy head technique handles all tricky scenarios gracefully:

Single Node

[1], n = 1 → Remove the only node. Dummy.next becomes null. Returns empty list.

Remove the Head

[1,2,3], n = 3 → The 3rd from end is node 1 (the head). Dummy.next skips to node 2. No special case needed.

Remove the Tail

[1,2,3], n = 1 → The last node is removed. Slow stops at node 2 and sets slow.next = null.

n Equals Length

[1,2], n = 2 → Same as removing the head. Fast advances past all nodes; slow stays at dummy.

🎯

Why the dummy node matters: Without it, removing the head requires special-case logic (checking if slow is still at the start). The dummy node ensures slow always has a next to rewire, even when the first real node must be removed.

Step 05

Full Annotated Java Code

/**
 * Definition for singly-linked list.
 * public 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) {

        // Dummy node simplifies edge cases (removing head)
        ListNode dummy = new ListNode(0, head);
        ListNode fast = dummy, slow = dummy;

        // Advance fast n+1 steps ahead of slow
        // This creates a gap so that when fast == null,
        // slow is right before the target node
        for (int i = 0; i <= n; i++)
            fast = fast.next;

        // Move both pointers until fast falls off the end
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // slow is now pointing to the node BEFORE the target
        // Skip over the target node
        slow.next = slow.next.next;

        // Return dummy.next (not head — head may have been removed!)
        return dummy.next;
    }
}

// Definition for singly-linked list.
// type ListNode struct {
//     Val  int
//     Next *ListNode
// }

func removeNthFromEnd(head *ListNode, n int) *ListNode {

    // Dummy node simplifies edge cases (removing head)
    dummy := &ListNode{Val: 0, Next: head}
    fast := dummy
    slow := dummy

    // Advance fast n+1 steps ahead of slow
    // This creates a gap so that when fast == nil,
    // slow is right before the target node
    for i := 0; i <= n; i++ {
        fast = fast.Next
    }

    // Move both pointers until fast falls off the end
    for fast != nil {
        fast = fast.Next
        slow = slow.Next
    }

    // slow is now pointing to the node BEFORE the target
    // Skip over the target node
    slow.Next = slow.Next.Next

    // Return dummy.Next (not head — head may have been removed!)
    return dummy.Next
}

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

def remove_nth_from_end(head: ListNode | None, n: int) -> ListNode | None:

    # Dummy node simplifies edge cases (removing head)
    dummy = ListNode(0, head)
    fast = dummy
    slow = dummy

    # Advance fast n+1 steps ahead of slow
    # This creates a gap so that when fast is None,
    # slow is right before the target node
    for _ in range(n + 1):
        fast = fast.next

    # Move both pointers until fast falls off the end
    while fast is not None:
        fast = fast.next
        slow = slow.next

    # slow is now pointing to the node BEFORE the target
    # Skip over the target node
    slow.next = slow.next.next

    # Return dummy.next (not head — head may have been removed!)
    return dummy.next

// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode { pub val: i32, pub next: Option<Box<ListNode>> }

impl Solution {
    pub fn remove_nth_from_end(
        head: Option<Box<ListNode>>,
        n: i32,
    ) -> Option<Box<ListNode>> {
        // Collect all node values into a Vec, then rebuild
        let mut vals: Vec<i32> = Vec::new();
        let mut curr = &head;
        while let Some(node) = curr {
            vals.push(node.val);
            curr = &node.next;
        }

        // Remove the nth from end
        let remove_idx = vals.len() - n as usize;
        vals.remove(remove_idx);

        // Rebuild the linked list from tail to head
        let mut result: Option<Box<ListNode>> = None;
        for &v in vals.iter().rev() {
            result = Some(Box::new(ListNode { val: v, next: result }));
        }
        result
    }
}

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number;
 *     next: ListNode | null;
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = val ?? 0;
 *         this.next = next ?? null;
 *     }
 * }
 */
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {

    // Dummy node simplifies edge cases (removing head)
    const dummy = new ListNode(0, head);
    let fast: ListNode | null = dummy;
    let slow: ListNode = dummy;

    // Advance fast n+1 steps ahead of slow
    // This creates a gap so that when fast === null,
    // slow is right before the target node
    for (let i = 0; i <= n; i++)
        fast = fast!.next;

    // Move both pointers until fast falls off the end
    while (fast !== null) {
        fast = fast.next;
        slow = slow.next!;
    }

    // slow is now pointing to the node BEFORE the target
    // Skip over the target node
    slow.next = slow.next!.next;

    // Return dummy.next (not head — head may have been removed!)
    return dummy.next;
}

Step 06

Interactive Demo

Enter a list and the value of n, then step through the algorithm to watch the two pointers in action.

⚙ Two-Pointer Visualizer

List values

n (from end)

Step 07

Complexity Analysis

Time

O(n)

Space

O(1)

We traverse the list exactly once. The fast pointer visits every node, and the slow pointer visits at most n - k nodes (where k is the removal index from the end). Total work is O(n) where n is the length of the list. We only use a constant number of pointer variables — no extra data structures.

Approach Breakdown

TWO-PASS

O(n) time

O(1) space

First pass traverses the entire list to count L nodes. Second pass walks to node (L - n) to rewire the pointer. Each pass is O(L), so total time is O(2L) = O(n). Only a counter and a pointer variable are needed.

ONE-PASS (TWO POINTERS)

O(n) time

O(1) space

The fast pointer advances n+1 steps ahead, then both pointers move in lockstep until fast reaches null. This single traversal covers at most L nodes total across both pointers, giving O(n). A dummy node and two pointer variables use O(1) space.

🎯

Same Big-O, but more elegant. The two-pointer "gap" trick uses two pointers spaced n nodes apart, achieving the same O(n) time and O(1) space as the two-pass approach — but in a single traversal. This matters for streaming scenarios or when the list is very large and cache locality is important.

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Losing head/tail while rewiring

Wrong move: Pointer updates overwrite references before they are saved.

Usually fails on: List becomes disconnected mid-operation.

Fix: Store next pointers first and use a dummy head for safer joins.

Moving both pointers on every comparison

Wrong move: Advancing both pointers shrinks the search space too aggressively and skips candidates.

Usually fails on: A valid pair can be skipped when only one side should move.

Fix: Move exactly one pointer per decision branch based on invariant.

Remove Nth NodeFrom End of List