How do you remove the n-th node from the end in one pass?

Put a dummy node before head and start fast and slow on it. Move fast n + 1 nodes ahead, then move both until fast is null; slow is then just before the target, so set slow.next = slow.next.next.

Why use a dummy node?

When n equals the list length, the node to remove is the head, which has no node before it. The dummy provides one, so removing the head needs no special case.

Why does fast move n + 1 nodes and not n?

The gap of n + 1 leaves slow one node before the target when fast falls off the end, which is where the unlink has to happen.

Remove Nth Node From End of List

Remove the nth node from the end of the list.

MediumSolve on LeetCode

Problem Understanding

Delete the node that sits n positions from the tail of a linked list, then return the list's head, which changes when the node removed is the first one.

Example: 1 -> 2 -> 3 -> 4 -> 5, n = 2. Remove 4. Result: 1 -> 2 -> 3 -> 5.

Attempt 1: Two Pass Algorithm

Iterate through the list to find the total length L.
The node to remove is at index L - n (from start).
Iterate again to the node just before L - n and change its next pointer.

This works but requires traversing the list twice.

Visualizing the Issue

Can we do this in One Pass? Imagine a stick of length n. If we slide this stick along the list so the front end touches the last node, the back end will be exactly at the node we need to remove!

The Intuition: Two Pointers (Gap Method)

Create a dummy node pointing to head (to handle removing the first node easily).
Move a fast pointer n + 1 steps ahead.
Move both fast and slow (initially at dummy) until fast reaches null.
slow is now pointing at the node before the target.
Delete target: slow.next = slow.next.next.

Interactive Walkthrough

N = 2 · GAP OF 3

DUMMY BEFORE HEAD

slow fast

dummy

→

→ NULL

Removed

—

result

Not returned yet

dummy.next = head. fast and slow both start on dummy, so removing the head needs no special case

fast moves ahead (1 of 3) to node 0 (1)

Values

Legend & Complexity

fast: n + 1 nodes ahead of slow

slow: stops just before the node to remove

The removed node, no longer reachable from dummy

The list returned from dummy.next

Time

O(n)

Space

O(1)

Watch fast open a gap of n + 1 nodes from dummy, then both pointers slide until fast is NULL — leaving slow just before the node to remove. The removed node ends up in its own row, reachable from nothing.

Dry Run Table

Input: 1 -> 2 -> 3 -> 4 -> 5, n = 2

Step	slow	fast	Action
Init	dummy	dummy	`dummy.next = head`
Gap	dummy	`3`	`fast` moves `n + 1 = 3` nodes: `1`, `2`, `3`
Move 1	`1`	`4`	Both move one node
Move 2	`2`	`5`	Both move one node
Move 3	`3`	`NULL`	`fast` has left the list
Remove	`3`	`NULL`	`slow.next = slow.next.next` unlinks `4`
Result	-	-	`1 -> 2 -> 3 -> 5`

The Solution Template

One-Pass Gap Method.

Remove Nth Node From End of List Code

1var removeNthFromEnd = function(head, n) {
2    let dummy = new ListNode(0);
3    dummy.next = head;
4    let fast = dummy;
5    let slow = dummy;
6    for (let i = 0; i <= n; i++) fast = fast.next;
7    while (fast) {
8        fast = fast.next;
9        slow = slow.next;
10    }
11    slow.next = slow.next.next;
12    return dummy.next;
13};

Edge Cases & Common Mistakes

Remove Head: If the node to remove is the first node, dummy usage is critical.
n = Length: Same as removing head.
Single Node: List becomes empty.

Summary

Using a dummy node and two pointers spaced n apart allows us to reach the node just before the n-th node from the end in a single pass.

Palindrome Linked List

Reorder List