Remove Nth Node From End of List — One-Pass Two-Pointer Solution

Problem Statement#

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

Constraints:

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

Example 1:

Input:  head = [1, 2, 3, 4, 5], n = 2
Output: [1, 2, 3, 5]
Explanation: The 2nd node from the end (value 4) is removed.

Example 2:

Input:  head = [1], n = 1
Output: []
Explanation: Only node is removed — empty list.

Example 3:

Input:  head = [1, 2], n = 1
Output: [1]
Explanation: The 1st from end (value 2) is removed.

Why This Problem Matters#

Remove Nth Node From End of List (LeetCode 19) is a Medium problem that Amazon, Google, and Facebook include in their linked list sections because it combines two important techniques: the dummy head sentinel and the n-gap two-pointer technique. Neither trick alone is remarkable, but composing them correctly under interview time pressure is where candidates separate.

The problem also teaches an important meta-skill: converting a "count from the end" requirement into a "count from the start" operation using pointer offset. Counting from the end requires knowing the total length — which you don't have upfront. The n-gap trick avoids computing the length explicitly: keep two pointers exactly n nodes apart. When the fast pointer hits the end, the slow pointer is at the predecessor of the target.

In real systems, this pattern appears in sliding window problems, buffer management, and any scenario where you need to maintain a fixed-distance relationship between two positions in a sequence without knowing the total length upfront.

The follow-up challenge — "do it in one pass" — is the real test. The two-pass solution (find length, then delete) is straightforward but not impressive. Solving it in one pass with the gap technique shows you've internalized the linked list two-pointer pattern.

The Core Insight#

Advance the fast pointer n + 1 steps from a dummy node placed before the head. Then advance both fast and slow together until fast is None. At that point, slow is exactly at the node before the target (the nth from the end).

Why n + 1 and not n? Because we want slow to stop at the predecessor of the target, not the target itself. We need slow.next = slow.next.next (skip the target), which requires being one position before it.

The dummy node makes this work even when the target is the head: the dummy is the predecessor of the head, so dummy.next = dummy.next.next (= head.next) is valid even for the first node.

Visual Dry Run#

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

Setup: dummy -> 1 -> 2 -> 3 -> 4 -> 5, both slow and fast start at dummy.

Phase 1: Advance fast n+1 = 3 steps

fast = node 3, slow = dummy.

Phase 2: Advance both until fast is None

Now slow = node 3 (value 3). The target is slow.next = node 4 (the 2nd from end).

Delete: slow.next = slow.next.next = node 5.

Output: 1 -> 2 -> 3 -> 5. Correct.

Head deletion case: [1, 2], n = 2

Advance fast 3 steps from dummy: dummy -> 1 -> 2 -> None (fast overflows! Only advance while fast exists)

Wait — if fast reaches None before completing n+1 steps, that's a problem. Let's be careful: the problem guarantees 1 <= n <= sz, so n+1 <= sz+1. After n+1 steps, fast is at index n+1 (0-indexed from dummy). For n = sz (head deletion), fast would be at the node just past the end — which is None. Then both advance: fast stays None, condition fails immediately, slow stays at dummy. dummy.next = dummy.next.next = None. Returns dummy.next = None. Correct!

Solution (Optimal)#

Python#

def removeNthFromEnd(head, n):
    dummy = ListNode(0)
    dummy.next = head
    fast = slow = dummy
 
    # Advance fast n+1 steps ahead of slow
    for _ in range(n + 1):
        fast = fast.next
 
    # Move both until fast reaches the end
    while fast:
        fast = fast.next
        slow = slow.next
 
    # slow is now at the predecessor of the target
    slow.next = slow.next.next
 
    return dummy.next

Time complexity: O(n) — one pass (the for loop + while loop together traverse the list once).

Space complexity: O(1) — dummy node and two pointer variables.

JavaScript#

var removeNthFromEnd = function(head, n) {
    const dummy = new ListNode(0);
    dummy.next = head;
    let fast = dummy, slow = dummy;
 
    // Advance fast n+1 steps
    for (let i = 0; i <= n; i++) {
        fast = fast.next;
    }
 
    // Move both until fast is null
    while (fast !== null) {
        fast = fast.next;
        slow = slow.next;
    }
 
    // Remove the target node
    slow.next = slow.next.next;
 
    return dummy.next;
};

Complexity:

Two-pass alternative (simpler to understand):

def removeNthFromEnd(head, n):
    # Pass 1: find length
    length = 0
    curr = head
    while curr:
        length += 1
        curr = curr.next
    
    # Pass 2: go to (length - n - 1)th node and skip next
    dummy = ListNode(0, head)
    curr = dummy
    for _ in range(length - n):
        curr = curr.next
    curr.next = curr.next.next
    return dummy.next

Common Mistakes#

1. Advancing fast n steps instead of n + 1. If you advance only n steps, slow stops at the target itself, not its predecessor. You'd then need slow = slow.next to get to the predecessor — but that loses the predecessor. Advance n + 1 steps so slow is already at the predecessor when the loop ends.

2. Not using a dummy node. Without a dummy, deleting the head requires a special case. If n equals the list length, the target is the head. With the dummy, slow stops at the dummy and dummy.next = dummy.next.next handles it uniformly.

3. Initializing fast at head instead of dummy. If fast starts at head, you advance n + 1 steps from head. But slow also starts at dummy. After fast reaches None, slow is one position too far. Start both at dummy.

4. Off-by-one in the gap. Draw this out: for n=2 and list [1,2,3,4,5], the target is node 4. Slow must stop at node 3. The gap between node 3 and None is 3 nodes (4, 5, None). That's n+1 steps. Verify your gap on a small example.

5. Returning dummy instead of dummy.next. The dummy node is not part of the list. Always return dummy.next.

Interview Tips#

1. Clarify the one-pass constraint: "I'll solve it in one pass using the n-gap technique. Fast starts n+1 ahead of slow. When fast hits None, slow is at the predecessor."

2. Draw the gap explicitly: On the whiteboard, draw fast and slow pointers with the gap between them. This visual makes the algorithm obvious and avoids off-by-one errors.

3. Verify the head deletion case: Walk through [1], n=1 in your head. Fast advances n+1=2 steps from dummy but hits None after 1 step. The while loop doesn't execute. Slow is at dummy. dummy.next = None. Return dummy.next = None. Correct.

4. State both approaches: "The two-pass approach finds the length first. The one-pass approach uses the n-gap technique. I'll use the one-pass approach since the interviewer asked for it."

5. n+1 not n: This is the most common mistake. Memorize: n+1 steps ahead so slow lands at the predecessor.

Follow-up Questions#

Q: What if n could be 0 (remove nothing)? The problem guarantees 1 <= n <= sz, so n = 0 doesn't occur. But if it did, advancing 1 step from dummy and then walking would result in slow at the last non-null position — and you'd still need a guard.

Q: What if the list has a cycle? If there's a cycle, fast never reaches None and the while loop runs forever. You'd need cycle detection first (Floyd's algorithm) before applying this technique.

Q: Can you do it recursively? Yes — a recursive approach can track position from the end using the call stack. When unwinding, count from the tail. When the counter hits n, skip that node. O(n) space for the call stack.

Q: What if you need to remove the k-th from the start? That's trivially a single traversal: advance k-1 steps, skip the next node. The "from the end" requirement is what makes the n-gap technique necessary.

Q: Can fast and slow be initialized at different starting positions? Yes — you can initialize fast at head (not dummy) and advance only n steps instead of n+1, then adjust. But this makes the head deletion case harder to handle cleanly. Starting both at dummy with n+1 advance is the cleanest formulation.

Key Takeaways#

• The dummy head sentinel eliminates the special case of deleting the head node — use it whenever the head might be deleted.
• Advance the fast pointer n + 1 steps ahead of slow (not n) so slow stops at the predecessor of the target.
• Start both pointers at the dummy node, not at head.
• When fast reaches None, slow is at the target's predecessor — execute slow.next = slow.next.next.
• The one-pass solution is O(sz) time and O(1) space — the for loop plus while loop together traverse the list once.
• This n-gap technique is a reusable pattern: wherever you need to maintain a fixed distance between two positions in a linked list without knowing the total length.