19. Remove Nth Node From End

MediumLinked Lists and Pointer ManipulationTwo pointers with a dummy headFixed-gap two pointers

Remove Nth Node From End

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

Open official problem prompt ↗

In plain English

Delete a single node identified by its distance from the tail, in one traversal, without knowing the list length in advance.

Picture it like this

Imagine two people walking a rope hand-over-hand, one starting n knots ahead. When the leader reaches the frayed end, the follower is standing exactly at the knot to cut.

Example

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
Why: The 2nd node from the end is the value 4, so removing it leaves 1 -> 2 -> 3 -> 5.

Constraints

The number of nodes is sz1 <= sz <= 300 <= Node.val <= 1001 <= n <= sz

Pattern lesson

See the pattern, then code

Fixed-gap two pointers

↗

Linked Lists and Pointer Manipulation

Reversal, cycle detection, merging, reordering, or O(1)-space sequence edits.. If a lead pointer is exactly n nodes ahead of a trailing pointer, then when the lead reaches the end the trailing pointer sits on the node just before the target, ready to splice it out.

New words, made simpleKnow these before the algorithm

Dummy (sentinel) node: A throwaway node placed before the head so that deleting the real head needs no special case.
Fixed gap: A constant distance maintained between two pointers as they advance together.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Two-pass length count

Correct but walks the list twice; the gap trick does it in one pass.

Traverse once to get length L, then traverse again to node L-n and unlink it.

Time O(n)Space O(1)

Best choiceFixed-gap two pointers with dummy

Single pass, O(1) extra space, and the dummy removes the edge case of deleting the head.

Open an n+1 gap, then slide both pointers until the leader falls off, leaving the follower before the target.

Time O(n)Space O(1)

The rule we keep true

Invariant

After the priming loop and throughout the main loop, fast is always exactly n+1 nodes ahead of slow, so slow trails the node to delete by one.

Why this is correct

Reasoning

The leader advances n+1 from dummy, so when it becomes None it has covered all sz+1 dummy-based positions; the follower, always n+1 behind, therefore rests on position (sz+1)-(n+1)-1 counted from dummy, which is the node immediately before the nth-from-end target.

The algorithm in three movesSay these aloud before coding

1Attach a dummy node before head so removing the first real node is uniform

gap: fast is n+1=3 ahead of slow

2Advance a fast pointer n+1 steps ahead of a slow pointer starting at dummy

slow stops at node 3 (before target)

3Move both one step at a time until fast falls off the end

slow.next = node 5, unlinking 4

4Relink slow.next to slow.next.next to unlink the target

5Return dummy.next

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readn+1 = 3 steps

2 · AskWhere does fast start?

3 · Update stateslow=dummy, fast=node3

4 · ResultFast is 3 ahead of slow.

Key takeaway

The trailing pointer lands on node 3, one before the target node 4 that gets removed.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3Sentinel setup
Dummy points to head so the first node is deletable with the same code path as any other.
2
Lines 4-6Open the gap
Advancing fast n+1 times guarantees slow ends one before the target rather than on it.
3
Lines 7-9Slide together
Both move in lockstep, preserving the gap until fast leaves the list.
4
Lines 10-11Splice and return
Bypass the target node and return the real head via dummy.next.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

List has one node and n = 1 (result is empty, why dummy matters)
Removing the head node (n equals length)
Removing the tail node (n = 1)

Common beginner mistakes

Advancing fast only n times instead of n+1, leaving slow on the target itself
Returning head instead of dummy.next when the head was removed
Forgetting the dummy and needing a special branch for head deletion

Check your understanding

Why prime fast by n+1 steps rather than n?

Remove Nth Node From End

Remove Nth Node From End

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Linked Lists and Pointer Manipulation