Partition List
Given a linked list and a number x, reorder the list so that every node holding a value smaller than x comes before every node holding a value greater than or equal to x . Inside each of the two groups, the nodes must keep the order they started in. The function takes a plain array plus x, builds the list inside, and returns a plain array. The clean way is to deal out the nodes into two separate chains as you walk the list once, then hook the end of the smaller chain onto the front of the bigger one.
Constraints
- The number of nodes is between 0 and 200
- -100 ≤ node value ≤ 100
- -200 ≤ x ≤ 200
- The order within each group must be preserved
Example
values = [1, 4, 3, 2, 5, 2], x = 3[1, 2, 2, 4, 3, 5]Explanation The values below 3, in their original order, are 1, 2 and 2. The values 3 or above, in their original order, are 4, 3 and 5.
In plain terms
- Partition
- Splitting a group into two parts by a rule. Here the rule is "value below x" against "value x or above".
- Stable order
- Nodes that land in the same group keep the order they had in the original list. Dealing them out front to back gives this for free.
- Dummy node
- A throwaway node that starts each chain, so you can attach nodes without checking whether the chain is still empty.
- Cutting the tail
- Setting the last node of the bigger chain to point at nothing. Without it the old arrows could loop back and the list would never end.
Each cell is one node of the original list; its label shows the chain it joined
Node 1 holds 1, which is below x = 3, so it starts the less chain.
What happens in this step
x = 3 node value = 1, and 1 < 3 less chain: 1 more chain: empty
Steps to visualize
- Walk the original list once, from head to tail.
- The frame marks the node being dealt out right now.
- A value below x joins the "less" chain; anything else joins the "more" chain.
- The label under each cell records which chain that node went to.
- At the end, the last node of the less chain points at the first node of the more chain.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
Node 1 holds 1, which is below x = 3, so it starts the less chain.
What happens in this step
x = 3 node value = 1, and 1 < 3 less chain: 1 more chain: empty
Solution
class ListNode {
constructor(val, next = null) {
this.val = val;
this.next = next;
}
}
function toList(values) {
let head = null;
for (let i = values.length - 1; i >= 0; i--) {
head = new ListNode(values[i], head);
}
return head;
}
function toArray(head) {
const out = [];
for (let node = head; node !== null; node = node.next) {
out.push(node.val);
}
return out;
}
function partition(values, x) {
const head = toList(values);
const lessHead = new ListNode(0);
const moreHead = new ListNode(0);
let less = lessHead;
let more = moreHead;
for (let node = head; node !== null; node = node.next) {
if (node.val < x) {
less.next = node;
less = less.next;
} else {
more.next = node;
more = more.next;
}
}
more.next = null;
less.next = moreHead.next;
return toArray(lessHead.next);
}- Time
- O(n)
- Space
- O(n)
Test cases
| Input | Expected | Covers |
|---|---|---|
values = [1, 4, 3, 2, 5, 2], x = 3 | [1, 2, 2, 4, 3, 5] | example from the description |
values = [2, 1], x = 2 | [1, 2] | smallest case where anything actually moves |
values = [], x = 1 | [] | empty list, nothing to partition |
values = [1, 2, 3], x = 10 | [1, 2, 3] | every node lands in the less chain |
values = [5, 6, 7], x = 1 | [5, 6, 7] | every node lands in the more chain |
values = [4, -2, 4, -5, 0, 4], x = 0 | [-2, -5, 4, 4, 0, 4] | negative values, repeats, and a value exactly equal to x |