Loading…

mediumLinked ListsLC #19Frequently asked

Remove Nth Node From End of List

Q: How do you solve Remove Nth Node From End of List using the Two Passes — Compute Length, Then Delete approach?

When to use it: State it first as the obvious baseline, then offer the one-pass two-pointer version the follow-up asks for. We turn 'nth from the end' into 'a known index from the front' by first measuring the list. **Pass 1 — measure.** Walk from head to null counting nodes; call the total `L`. Now the node to remove is the `(L − n)`-th from the front (0-based), and its predecessor is at index `L − n − 1`. **Pass 2 — delete.** Start at a dummy node placed before the head and step forward `L − n` times. That lands us on the predecessor of the target (the dummy contributes the `−1` so the arithmetic is clean even when the head is removed). A single `prev.next = prev.next.next` unlinks the target. **Why the dummy still matters here.** If the head is the node to remove (`n == L`), then `L − n = 0` and we step zero times, leaving us on the dummy whose `next` is the head — exactly the predecessor we need. Without the dummy we'd special-case `head = head.next`. **Why we still prefer one pass.** This is perfectly correct and easy to reason about, but it touches the list twice. The follow-up explicitly asks for a single pass, which the gap-based two-pointer method delivers — same complexity class, one traversal. Time complexity: O(n). Space complexity: O(1).

Q: How do you solve Remove Nth Node From End of List using the One Pass — Two Pointers with a Gap of n (Optimal) approach?

When to use it: The answer the follow-up wants. Phrase it as 'keep two pointers n apart so when fast hits the end, slow is right before the target'. We maintain a constant gap of `n` nodes between two pointers so that the moment `fast` reaches the end, `slow` is automatically parked at the right spot. **Set up the dummy and the gap.** Both `slow` and `fast` start at a dummy node placed before `head`. We advance `fast` exactly `n` times. Now `fast` is `n` nodes ahead of `slow`. **March in lockstep.** Move both pointers one step at a time while `fast.next != null`. Because the gap never changes, when `fast` lands on the *last* node, `slow` is sitting exactly `n + 1` nodes from the end counting from the dummy — i.e. on the node *immediately before* the nth-from-end target. That predecessor position is precisely what we need to splice. **Why `fast.next != null` and not `fast != null`.** We want `slow` to stop on the predecessor, not on the target itself. Stopping `fast` on the last node (rather than walking it to null) leaves `slow` one short of the target — exactly one node before it. Using `fast != null` would overshoot `slow` by one and delete the wrong node. **Why the dummy is essential.** Consider `n == length` (remove the head). The gap setup puts `fast` on the last node right away while `slow` is still on the dummy; the lockstep loop doesn't run, and `slow.next = slow.next.next` neatly drops the head. Returning `dummy.next` then yields the new head. No special-casing — the dummy absorbs the edge. Time complexity: O(n). Space complexity: O(1).

LCPractice

Linked List · 5 of 24 · 9 min

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

Follow up: Could you do this in one pass?

In plain English

Count n from the tail (n = 1 is the last node) and unlink that node. The constraint guarantees n is valid, so the node always exists. The head itself can be the node to remove — that's the case a dummy node makes painless.

Examples

Example 1

Input: head = [1, 2, 3, 4, 5], n = 2
Output: [1, 2, 3, 5]
Note: The 2nd node from the end is 4; removing it links 3 → 5.

Example 2

Input: head = [1], n = 1
Output: []
Note: The only node is the 1st from the end; removing it yields the empty list — the dummy node makes this clean.

Example 3

Input: head = [1, 2], n = 2
Output: [2]
Note: The 2nd from the end is the head (1); the dummy lets us splice it out and return dummy.next = node 2.

Constraints

The number of nodes in the list is sz
1 ≤ sz ≤ 30
0 ≤ Node.val ≤ 100
1 ≤ n ≤ sz (n is always valid)

Clarifying questions4First question: Is n guaranteed to be within bounds?Explore questions

Q1.Is n guaranteed to be within bounds?
Yes — the constraints say 1 ≤ n ≤ sz, so I don't need to validate n against the list length.
Q2.Can n point at the head (n equals the list length)?
Yes, and that's exactly why I use a dummy node before the head — removing the first node then needs no special case.
Q3.Should I do it in one pass or is two passes acceptable?
The follow-up asks for one pass; the two-pointer gap method achieves it. I can mention the simpler two-pass length-then-delete as the baseline.
Q4.Is n counted 1-based from the end?
Yes — n = 1 means the last node, n = 2 the second-to-last, and so on.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Use two pointers separated by a gap of n nodes, both starting from a dummy node placed before the head. Advance fast by n steps first, then move fast and slow together until fast hits the end. Slow now sits exactly one node before the target, so slow.next = slow.next.next splices it out. The dummy node makes removing the head itself a non-special case. One pass, O(n) time, O(1) space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can do it in one pass with the gap-of-n two-pointer trick, and whether you use a dummy node to handle removing the head without a special branch.

Where candidates slip

Stopping slow on the target instead of one before it, or not using a dummy node and crashing/returning wrong when the head is removed.

How to stand out

Do it in a single pass, justify the dummy node by walking through the 'remove the head' case, and confirm the loop condition leaves slow exactly one node before the target.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Two Passes — Compute Length, Then Delete	`O(n)`	`O(1)`	State it first as the obvious baseline, then offer the one-pass two-pointer version the follow-up asks for.	Read
2	One Pass — Two Pointers with a Gap of n (Optimal)Optimal	`O(n)`	`O(1)`	The answer the follow-up wants. Phrase it as 'keep two pointers n apart so when fast hits the end, slow is right before the target'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewRemove nth node from the endOne pass required?YesNo / simplerExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Two Passes — Compute Length, Then Delete

TimeO(n)SpaceO(1)

State it first as the obvious baseline, then offer the one-pass two-pointer version the follow-up asks for.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If you knew the list's length L, which position from the front is the nth node from the end?

2Hint 2Explore hint

The nth-from-end node is at index L - n from the front (0-based). To delete it you need the node just before it, at index L - n - 1.

3Hint 3Explore hint

Pass 1: walk the whole list to get L. Pass 2: from a dummy, step L - n times to reach the predecessor, then splice.

A · Core idea

We turn 'nth from the end' into 'a known index from the front' by first measuring the list.

Pass 1 — measure. Walk from head to null counting nodes; call the total L. Now the node to remove is the (L − n)-th from the front (0-based), and its predecessor is at index L − n − 1.

Pass 2 — delete. Start at a dummy node placed before the head and step forward L − n times. That lands us on the predecessor of the target (the dummy contributes the −1 so the arithmetic is clean even when the head is removed). A single prev.next = prev.next.next unlinks the target.

Why the dummy still matters here. If the head is the node to remove (n == L), then L − n = 0 and we step zero times, leaving us on the dummy whose next is the head — exactly the predecessor we need. Without the dummy we'd special-case head = head.next.

Why we still prefer one pass. This is perfectly correct and easy to reason about, but it touches the list twice. The follow-up explicitly asks for a single pass, which the gap-based two-pointer method delivers — same complexity class, one traversal.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

pass 1

count nodes

StateL = 5

Final result[1, 2, 3, 5]

C · Code with teaching comments

Reference implementation previewpublic class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; }Explore the full code

solution.javaJava

Two Passes — Compute Length, Then Delete — reference

4 teaching notes

1
public class ListNode {
2
    int val;
3
    ListNode next;
4
    ListNode() {}
5
    ListNode(int val) { this.val = val; }
6
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
7
}
8
 
9
public ListNode removeNthFromEnd(ListNode head, int n) {
10
    int length = 0;
11
    // Pass 1: count the nodes to get the total length L.
12
    for (ListNode cur = head; cur != null; cur = cur.next) {
13
        length++;
14
    }
15
    // Dummy before head so removing the first node needs no special case.
16
    ListNode dummy = new ListNode(0, head);
17
    ListNode prev = dummy;
18
    // Step from dummy to the predecessor of the target (index L-n-1 in the real list).
19
    for (int i = 0; i < length - n; i++) {
20
        prev = prev.next;
21
    }
22
    // Splice out the target node by skipping over it.
23
    prev.next = prev.next.next;
24
    return dummy.next;
25
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.25 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

Converting an end-relative index into a front-relative one via the length is the most direct reading of the problem. It's the baseline that motivates the slicker single-pass trick, and the dummy node already earns its keep on the head-removal case.

ComplexityO(n) time, O(1) space — Two linear scans (length, then predecessor) → O(2n) = O(n) time. Only a counter and a couple of pointers → O(1) space.

E · Edge cases and pitfalls3Off-by-one: stepping length - n - 1 or length - n + 1 instead of length - n from the dummy.Explore edge cases

Pitfalls

Off-by-one: stepping length - n - 1 or length - n + 1 instead of length - n from the dummy.
Not using a dummy and mishandling removal of the head node.
Computing length but forgetting the head could be the target.

03.2

Approach 2 of 2 · Optimal

One Pass — Two Pointers with a Gap of n (Optimal)

TimeO(n)SpaceO(1)

The answer the follow-up wants. Phrase it as 'keep two pointers n apart so when fast hits the end, slow is right before the target'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You want the node n from the end, but you only discover the end by walking there. What if a second pointer were already n nodes ahead of the first?

2Hint 2Explore hint

Put both pointers on a dummy node before the head. Advance fast n steps to create a gap of exactly n.

3Hint 3Explore hint

Now move fast and slow together until fast.next is null. The gap is preserved, so slow stops exactly one node before the target — splice with slow.next = slow.next.next.

A · Core idea

We maintain a constant gap of n nodes between two pointers so that the moment fast reaches the end, slow is automatically parked at the right spot.

Set up the dummy and the gap. Both slow and fast start at a dummy node placed before head. We advance fast exactly n times. Now fast is n nodes ahead of slow.

March in lockstep. Move both pointers one step at a time while fast.next != null. Because the gap never changes, when fast lands on the last node, slow is sitting exactly n + 1 nodes from the end counting from the dummy — i.e. on the node immediately before the nth-from-end target. That predecessor position is precisely what we need to splice.

Why `fast.next != null` and not `fast != null`. We want slow to stop on the predecessor, not on the target itself. Stopping fast on the last node (rather than walking it to null) leaves slow one short of the target — exactly one node before it. Using fast != null would overshoot slow by one and delete the wrong node.

Why the dummy is essential. Consider n == length (remove the head). The gap setup puts fast on the last node right away while slow is still on the dummy; the lockstep loop doesn't run, and slow.next = slow.next.next neatly drops the head. Returning dummy.next then yields the new head. No special-casing — the dummy absorbs the edge.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Array state

gap opened

fast advanced n=2 from dummy

slow ↓

[0]

[1]

fast ↓

[2]

[3]

[4]

[5]

Current pointerResolved stateNot processed

Final result[1, 2, 3, 5]

C · Code with teaching comments

solution.javaJava

One Pass — Two Pointers with a Gap of n (Optimal) — optimal

5 teaching notes

1
public ListNode removeNthFromEnd(ListNode head, int n) {
2
    // Sentinel before head; makes removing the head identical to removing any other
3
    // node.
4
    ListNode dummy = new ListNode(0, head);
5
    ListNode slow = dummy, fast = dummy;
6
    // Advance fast n steps to open a fixed gap of n between fast and slow.
7
    for (int i = 0; i < n; i++) {
8
        fast = fast.next;
9
    }
10
    // fast.next (not fast) so slow halts ONE node before the target, never on it.
11
    while (fast.next != null) {
12
        slow = slow.next;
13
        fast = fast.next;
14
    }
15
    // slow is the predecessor; skip over the nth-from-end node to unlink it.
16
    slow.next = slow.next.next;
17
    // Return dummy.next — head may have been the removed node.
18
    return dummy.next;
19
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.19 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

A fixed gap between two pointers is a portable trick: it answers 'nth from the end' without ever computing the length. Pair it with a dummy node and head deletion stops being a special case — the two ideas together make linked-list editing branch-free.

ComplexityO(n) time, O(1) space — fast traverses the list once (n steps to open the gap plus the rest), slow trails it — a single combined pass of O(n). Two pointers and a dummy → O(1) space.

E · Edge cases and pitfalls6head = [1], n = 1 — fast steps to node 1; loop skipped (fast.next null); slow on dummy; slow.next = null → returns empty list.Explore edge cases

Edge cases handled

head = [1], n = 1fast steps to node 1; loop skipped (fast.next null); slow on dummy; slow.next = null → returns empty list.
head = [1, 2], n = 2fast steps 2 from dummy to node 2; loop skipped since fast.next is null; slow stays on dummy → removes the head, returns [2].
head = [1, 2, 3], n = 3Remove the head: fast ends on last node immediately, slow stays on dummy, dummy.next becomes node 2.

Pitfalls

Using while (fast != null) instead of fast.next — slow overshoots and deletes the wrong node.
Omitting the dummy and crashing when the head must be removed.
Advancing fast n+1 or n-1 times, breaking the gap arithmetic.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0, head); ListNode slow = dummy, fast = dummy; for (int i = 0; i < n; i++) { fast = fast.next;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Wrong loop condition lands slow on the target

To splice you need the node BEFORE the target. Walking fast all the way to null moves slow one node too far.

Explore the code comparison

Don't write this

for (int i = 0; i < n; i++) fast = fast.next;
while (fast != null) {       // overshoots
    slow = slow.next;
    fast = fast.next;
}
slow.next = slow.next.next;  // slow is now ON the target

Write this instead

for (int i = 0; i < n; i++) fast = fast.next;
while (fast.next != null) {
    slow = slow.next;
    fast = fast.next;
}
slow.next = slow.next.next;

No dummy node breaks head removal

If the head is the nth-from-end node, there's no predecessor to splice from. A dummy gives the head a predecessor.

Explore the code comparison

Don't write this

slow = fast = head
for _ in range(n):
    fast = fast.next
while fast.next:
    slow = slow.next
    fast = fast.next
slow.next = slow.next.next  # fails / wrong when head is the target
return head

Write this instead

dummy = ListNode(0, head)
slow = fast = dummy
for _ in range(n):
    fast = fast.next
while fast.next:
    slow = slow.next
    fast = fast.next
slow.next = slow.next.next
return dummy.next

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Two pointers with a fixed gap of n + a dummy node

Code pattern to memorize

dummy = ListNode(0, head)
slow = fast = dummy
for _ in range(n): fast = fast.next   # open the gap
while fast.next: slow = slow.next; fast = fast.next
slow.next = slow.next.next            # unlink target
return dummy.next

Rules to remember

1Anchor both pointers at a dummy before head so deleting the first node uses the same code path.
2Advance fast exactly n steps to open the gap, then move both until fast.next is null — slow lands just before the target.
3Return dummy.next, not head — the head may have been the node you removed.
4Loop condition is fast.next != null (not fast != null) so slow stops one node before the target, not on it.
5The gap of n between slow and fast is the whole trick: it converts 'nth from the end' into 'nth ahead of slow'.

Use this pattern when

Delete or locate a node a fixed distance from the end in a single pass
Any 'nth from the end' query on a singly linked list without precomputing the length
Sliding a fixed-width window of pointers along a list
Problems where a dummy node removes head-deletion edge cases

Choose another pattern when

You already know the length cheaply → a single index from the front is simpler
It's a doubly linked list with a tail pointer → walk back n from the tail directly
You need every node's distance-from-end, not just one → a length pass may be clearer

Interview takeaway

Opening a fixed gap between two pointers turns a two-pass length-then-delete into one clean pass. The dummy-node trick that neutralises head deletion shows up across linked-list editing problems.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternFixed-gap two pointers plus the dummy-node idiom. Reach for the gap whenever a query is relative to the end of a list, and the dummy whenever a deletion might hit the head. Same toolkit as Remove Linked List Elements and Delete the Middle Node.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Middle of the Linked List
Same two-pointer idea but with fast moving twice as fast instead of a fixed gap.
Delete the Middle Node of a Linked List
Coming soon
Slow/fast to find the middle, keep a prev pointer, then splice it out.
Remove Linked List Elements
Coming soon
Dummy node + single pass, removing every node matching a value.
Remove Duplicates from Sorted List II
Coming soon
Dummy node and a prev pointer to splice out runs of duplicate values.

Same pattern

←

Reorder List

Continue · Next problem

Copy List with Random Pointer

mediumLinked ListsLC #19Frequently asked

Remove Nth Node From End of List

LCPractice

Linked List · 5 of 24 · 9 min

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

Follow up: Could you do this in one pass?

In plain English

Examples

Example 1

Input: head = [1, 2, 3, 4, 5], n = 2
Output: [1, 2, 3, 5]
Note: The 2nd node from the end is 4; removing it links 3 → 5.

Example 2

Input: head = [1], n = 1
Output: []
Note: The only node is the 1st from the end; removing it yields the empty list — the dummy node makes this clean.

Example 3

Input: head = [1, 2], n = 2
Output: [2]
Note: The 2nd from the end is the head (1); the dummy lets us splice it out and return dummy.next = node 2.

Constraints

The number of nodes in the list is sz
1 ≤ sz ≤ 30
0 ≤ Node.val ≤ 100
1 ≤ n ≤ sz (n is always valid)

Clarifying questions4First question: Is n guaranteed to be within bounds?Explore questions

Q1.Is n guaranteed to be within bounds?
Yes — the constraints say 1 ≤ n ≤ sz, so I don't need to validate n against the list length.
Q2.Can n point at the head (n equals the list length)?
Yes, and that's exactly why I use a dummy node before the head — removing the first node then needs no special case.
Q3.Should I do it in one pass or is two passes acceptable?
The follow-up asks for one pass; the two-pointer gap method achieves it. I can mention the simpler two-pass length-then-delete as the baseline.
Q4.Is n counted 1-based from the end?
Yes — n = 1 means the last node, n = 2 the second-to-last, and so on.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can do it in one pass with the gap-of-n two-pointer trick, and whether you use a dummy node to handle removing the head without a special branch.

Where candidates slip

Stopping slow on the target instead of one before it, or not using a dummy node and crashing/returning wrong when the head is removed.

How to stand out

Do it in a single pass, justify the dummy node by walking through the 'remove the head' case, and confirm the loop condition leaves slow exactly one node before the target.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Two Passes — Compute Length, Then Delete	`O(n)`	`O(1)`	State it first as the obvious baseline, then offer the one-pass two-pointer version the follow-up asks for.	Read
2	One Pass — Two Pointers with a Gap of n (Optimal)Optimal	`O(n)`	`O(1)`	The answer the follow-up wants. Phrase it as 'keep two pointers n apart so when fast hits the end, slow is right before the target'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Two Passes — Compute Length, Then Delete

TimeO(n)SpaceO(1)

State it first as the obvious baseline, then offer the one-pass two-pointer version the follow-up asks for.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If you knew the list's length L, which position from the front is the nth node from the end?

2Hint 2Explore hint

The nth-from-end node is at index L - n from the front (0-based). To delete it you need the node just before it, at index L - n - 1.

3Hint 3Explore hint

Pass 1: walk the whole list to get L. Pass 2: from a dummy, step L - n times to reach the predecessor, then splice.

A · Core idea

We turn 'nth from the end' into 'a known index from the front' by first measuring the list.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

pass 1

count nodes

StateL = 5

Final result[1, 2, 3, 5]

C · Code with teaching comments

Reference implementation previewpublic class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; }Explore the full code

solution.javaJava

Two Passes — Compute Length, Then Delete — reference

4 teaching notes

1
public class ListNode {
2
    int val;
3
    ListNode next;
4
    ListNode() {}
5
    ListNode(int val) { this.val = val; }
6
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
7
}
8
 
9
public ListNode removeNthFromEnd(ListNode head, int n) {
10
    int length = 0;
11
    // Pass 1: count the nodes to get the total length L.
12
    for (ListNode cur = head; cur != null; cur = cur.next) {
13
        length++;
14
    }
15
    // Dummy before head so removing the first node needs no special case.
16
    ListNode dummy = new ListNode(0, head);
17
    ListNode prev = dummy;
18
    // Step from dummy to the predecessor of the target (index L-n-1 in the real list).
19
    for (int i = 0; i < length - n; i++) {
20
        prev = prev.next;
21
    }
22
    // Splice out the target node by skipping over it.
23
    prev.next = prev.next.next;
24
    return dummy.next;
25
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.25 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(1) space — Two linear scans (length, then predecessor) → O(2n) = O(n) time. Only a counter and a couple of pointers → O(1) space.

E · Edge cases and pitfalls3Off-by-one: stepping length - n - 1 or length - n + 1 instead of length - n from the dummy.Explore edge cases

Pitfalls

Off-by-one: stepping length - n - 1 or length - n + 1 instead of length - n from the dummy.
Not using a dummy and mishandling removal of the head node.
Computing length but forgetting the head could be the target.

03.2

Approach 2 of 2 · Optimal

One Pass — Two Pointers with a Gap of n (Optimal)

TimeO(n)SpaceO(1)

The answer the follow-up wants. Phrase it as 'keep two pointers n apart so when fast hits the end, slow is right before the target'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You want the node n from the end, but you only discover the end by walking there. What if a second pointer were already n nodes ahead of the first?

2Hint 2Explore hint

Put both pointers on a dummy node before the head. Advance fast n steps to create a gap of exactly n.

3Hint 3Explore hint

Now move fast and slow together until fast.next is null. The gap is preserved, so slow stops exactly one node before the target — splice with slow.next = slow.next.next.

A · Core idea

We maintain a constant gap of n nodes between two pointers so that the moment fast reaches the end, slow is automatically parked at the right spot.

Set up the dummy and the gap. Both slow and fast start at a dummy node placed before head. We advance fast exactly n times. Now fast is n nodes ahead of slow.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Array state

gap opened

fast advanced n=2 from dummy

slow ↓

[0]

[1]

fast ↓

[2]

[3]

[4]

[5]

Current pointerResolved stateNot processed

Final result[1, 2, 3, 5]

C · Code with teaching comments

solution.javaJava

One Pass — Two Pointers with a Gap of n (Optimal) — optimal

5 teaching notes

1
public ListNode removeNthFromEnd(ListNode head, int n) {
2
    // Sentinel before head; makes removing the head identical to removing any other
3
    // node.
4
    ListNode dummy = new ListNode(0, head);
5
    ListNode slow = dummy, fast = dummy;
6
    // Advance fast n steps to open a fixed gap of n between fast and slow.
7
    for (int i = 0; i < n; i++) {
8
        fast = fast.next;
9
    }
10
    // fast.next (not fast) so slow halts ONE node before the target, never on it.
11
    while (fast.next != null) {
12
        slow = slow.next;
13
        fast = fast.next;
14
    }
15
    // slow is the predecessor; skip over the nth-from-end node to unlink it.
16
    slow.next = slow.next.next;
17
    // Return dummy.next — head may have been the removed node.
18
    return dummy.next;
19
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.19 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6head = [1], n = 1 — fast steps to node 1; loop skipped (fast.next null); slow on dummy; slow.next = null → returns empty list.Explore edge cases

Edge cases handled

head = [1], n = 1fast steps to node 1; loop skipped (fast.next null); slow on dummy; slow.next = null → returns empty list.
head = [1, 2], n = 2fast steps 2 from dummy to node 2; loop skipped since fast.next is null; slow stays on dummy → removes the head, returns [2].
head = [1, 2, 3], n = 3Remove the head: fast ends on last node immediately, slow stays on dummy, dummy.next becomes node 2.

Pitfalls

Using while (fast != null) instead of fast.next — slow overshoots and deletes the wrong node.
Omitting the dummy and crashing when the head must be removed.
Advancing fast n+1 or n-1 times, breaking the gap arithmetic.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Wrong loop condition lands slow on the target

To splice you need the node BEFORE the target. Walking fast all the way to null moves slow one node too far.

Explore the code comparison

Don't write this

for (int i = 0; i < n; i++) fast = fast.next;
while (fast != null) {       // overshoots
    slow = slow.next;
    fast = fast.next;
}
slow.next = slow.next.next;  // slow is now ON the target

Write this instead

for (int i = 0; i < n; i++) fast = fast.next;
while (fast.next != null) {
    slow = slow.next;
    fast = fast.next;
}
slow.next = slow.next.next;

No dummy node breaks head removal

If the head is the nth-from-end node, there's no predecessor to splice from. A dummy gives the head a predecessor.

Explore the code comparison

Don't write this

slow = fast = head
for _ in range(n):
    fast = fast.next
while fast.next:
    slow = slow.next
    fast = fast.next
slow.next = slow.next.next  # fails / wrong when head is the target
return head

Write this instead

dummy = ListNode(0, head)
slow = fast = dummy
for _ in range(n):
    fast = fast.next
while fast.next:
    slow = slow.next
    fast = fast.next
slow.next = slow.next.next
return dummy.next

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Two pointers with a fixed gap of n + a dummy node

Code pattern to memorize

dummy = ListNode(0, head)
slow = fast = dummy
for _ in range(n): fast = fast.next   # open the gap
while fast.next: slow = slow.next; fast = fast.next
slow.next = slow.next.next            # unlink target
return dummy.next

Rules to remember

1Anchor both pointers at a dummy before head so deleting the first node uses the same code path.
2Advance fast exactly n steps to open the gap, then move both until fast.next is null — slow lands just before the target.
3Return dummy.next, not head — the head may have been the node you removed.
4Loop condition is fast.next != null (not fast != null) so slow stops one node before the target, not on it.
5The gap of n between slow and fast is the whole trick: it converts 'nth from the end' into 'nth ahead of slow'.

Use this pattern when

Delete or locate a node a fixed distance from the end in a single pass
Any 'nth from the end' query on a singly linked list without precomputing the length
Sliding a fixed-width window of pointers along a list
Problems where a dummy node removes head-deletion edge cases

Choose another pattern when

You already know the length cheaply → a single index from the front is simpler
It's a doubly linked list with a tail pointer → walk back n from the tail directly
You need every node's distance-from-end, not just one → a length pass may be clearer

Interview takeaway

Opening a fixed gap between two pointers turns a two-pass length-then-delete into one clean pass. The dummy-node trick that neutralises head deletion shows up across linked-list editing problems.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Middle of the Linked List
Same two-pointer idea but with fast moving twice as fast instead of a fixed gap.
Delete the Middle Node of a Linked List
Coming soon
Slow/fast to find the middle, keep a prev pointer, then splice it out.
Remove Linked List Elements
Coming soon
Dummy node + single pass, removing every node matching a value.
Remove Duplicates from Sorted List II
Coming soon
Dummy node and a prev pointer to splice out runs of duplicate values.

Same pattern

←

Reorder List

Continue · Next problem

Copy List with Random Pointer