Pivot Partition of a Chain
MediumLinked List
Problem
A triage desk keeps patients in a linked list ordered by arrival, each with a severity score. Every patient with a score below x must be moved ahead of every patient with a score of x or more.
Given the head and x, partition the list that way while keeping the original relative order inside each of the two groups, and return the head.
Example 1
- Input:
- head = [5, 1, 7, 2, 5, 3], x = 5
- Output:
- [1, 2, 3, 5, 7, 5]
Below 5: 1, 2, 3 in arrival order; then 5, 7, 5 in arrival order.
Example 2
- Input:
- head = [2, 1], x = 2
- Output:
- [1, 2]
Constraints
- 0 ≤ number of nodes ≤ 10^4
- -100 ≤ node.val ≤ 100
- -200 ≤ x ≤ 200
Hint
Show the first hint
You are sorting into just two buckets, and order inside each bucket must not change.
Walkthrough
How to approach it
01Clarify before coding
- Where do nodes equal to x go? With the 'x or more' group.
- Must the order inside each group be kept? Yes, the partition is stable.
- Relink or copy? Relink the existing nodes.
02Brute force
Collect values below x and values from x up into two arrays, concatenate, and write them back.
Cost: O(n) time and O(n) extra space; correct but wastes memory and moves values instead of nodes.
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.