Drop the Middle Node
MediumLinked List
Problem
A relay chain of servers is a singly linked list of n nodes. The node at 0-based index ⌊n / 2⌋ is the middle one, and it is being decommissioned.
Given the head, remove the middle node in one pass and return the head. A single-node list becomes empty.
Example 1
- Input:
- head = [1, 3, 4, 7, 1, 2, 6]
- Output:
- [1, 3, 4, 1, 2, 6]
n = 7, so index 3 (value 7) is removed.
Example 2
- Input:
- head = [2, 1]
- Output:
- [2]
n = 2, so index 1 is removed.
Constraints
- 1 ≤ number of nodes ≤ 10^5
- 1 ≤ node.val ≤ 10^5
Hint
Show the first hint
To remove a node you must stop on its predecessor. Which fast/slow variant lands one node earlier?
Walkthrough
How to approach it
01Clarify before coding
- Which middle for even n? Index n / 2, the second of the two middles.
- What about one node? The list becomes empty.
- One pass required? That is the goal.
02Brute force
Count n in one pass, then walk ⌊n / 2⌋ - 1 steps and unlink the next node.
Cost: O(n) time and O(1) space, but two passes.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.