Remove Nth Node From End of List

The problem. Given the head of a linked list, remove the nth node from the end and return the head. n = 1 means the last node.

1 -> 2 -> 3 -> 4 -> 5 with n = 2: counting from the end, 5 is 1st and 4 is 2nd, so 4 is removed and 3 now points to 5.

Example

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

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

Two difficulties: a singly linked list can't count backwards from the end, and deleting a node means changing the arrow of the node before it. When the node to delete is the head, there is no node before it — a dummy node fixes that.

Free account

Keep reading. It's free.

Sign up to read the rest of this lesson: 5 more sections, 2 drawings, a dry-run simulator and code in JavaScript, Python, Java and C++.

Still to come

1. Brute force: copy the nodes into an array
2. Optimal: count, then walk to the node before the target
3. Best solution: a two-pointer gap
Comparing the three approaches
Edge cases to test

Prev Next

Mark completed

Was this helpful?

StackLast-in, first-out — the structure behind call stacks, undo history, and expression parsing.6 lessons · 13 problems
QueueFirst-in, first-out — the structure behind task scheduling and breadth-first traversal.4 lessons · 5 problems
ArraysContiguous, indexable memory — the foundation almost every other data structure builds on.12 lessons · 16 problems

Remove Nth Node From End of List

Example

Keep reading. It's free.

Keep exploring