Partition List
Last Updated: March 29, 2026
Understanding the Problem
This problem is essentially asking us to do a stable partition on a linked list. We need to split the nodes into two groups based on a threshold value x: nodes with values less than x, and nodes with values greater than or equal to x. Within each group, the original order must be preserved.
The word "preserve" is critical here. If we just moved nodes around carelessly, we might get all the right values in the right half, but in the wrong order. For example, with [1, 4, 3, 2, 5, 2] and x = 3, we can't output [2, 2, 1, 3, 5, 4] even though that also has all the "less than 3" values first. The relative order within each group has to match the original list.
The key observation is that we're not sorting. We're partitioning. Two nodes that are both less than x should appear in the same relative order as they did in the original list. This means we need a stable approach, not just any rearrangement.
Key Constraints:
0 <= n <= 200-> With at most 200 nodes, even an O(n^2) solution would be nearly instant. But there's no reason to go beyond O(n) for a linked list partition.-100 <= Node.val <= 100-> Small value range. Values can be negative, and they can equalx. The condition is strictly "less than," so nodes equal toxgo into the "greater than or equal to" group.-200 <= x <= 200-> The partition valuexmight not even appear in the list. It could also be smaller than all values or larger than all values.
Approach 1: Collect into Array and Rebuild
Intuition
The most straightforward way to think about this: traverse the linked list, collect all node values into an array, partition the array (preserving order), and then build a new linked list from the partitioned values.
This sidesteps all the tricky pointer manipulation. We just work with arrays, which are easier to reason about, and then convert back.
Algorithm
- Traverse the linked list and collect all values into an array.
- Create two arrays: one for values less than
x, one for values greater than or equal tox. - Concatenate the two arrays (less-than first, then greater-or-equal).
- Build a new linked list from the concatenated array and return it.
Example Walkthrough
Input:
After partitioning into two groups:
Concatenate and rebuild:
Code
- Time Complexity: O(n). We traverse the list once to collect values (O(n)), and then iterate through all values to build the new list (O(n)). Total is O(n).
- Space Complexity: O(n). We store all node values in arrays, and create entirely new nodes for the result list.
This approach works correctly but uses extra memory by creating new nodes. What if we rearranged the existing nodes by manipulating their next pointers instead?
Approach 2: Two Dummy Lists (Optimal)
Intuition
Instead of copying values, we can rewire the existing nodes into two separate chains. One chain collects all nodes with values less than x, and the other collects all nodes with values greater than or equal to x. Then we just connect the tail of the first chain to the head of the second chain.
The trick that makes this clean is using dummy head nodes. Without dummy nodes, we'd need special-case logic for the first node added to each chain. A dummy node acts as a placeholder so we can always append to tail.next without checking if the chain is empty.
We're essentially unzipping the original list into two independent chains and then zipping them back in the right order. Because we process nodes from left to right and always append to the tail, the relative order within each chain matches the original list. That's what makes this a stable partition.
The dummy nodes eliminate all the edge cases. Without them, we'd need to check "is this the first node in the chain?" every time we append. The dummy gives us a guaranteed non-null tail to append to from the very start.
Algorithm
- Create two dummy nodes:
lessHeadandgreaterHead. These will serve as the anchors for our two chains. - Initialize two tail pointers:
lessTailandgreaterTail, both pointing to their respective dummy nodes. - Traverse the original list. For each node:
- If
node.val < x, append it to the "less" chain. - Otherwise, append it to the "greater" chain.
- Connect the two chains: set
lessTail.next = greaterHead.next(skip the dummy). - Terminate the list: set
greaterTail.next = nullto avoid cycles. - Return
lessHead.next(skip the dummy).
Example Walkthrough
Code
- Time Complexity: O(n). We traverse the entire list exactly once, doing O(1) work per node. The final connection step is also O(1).
- Space Complexity: O(1). We only use a constant number of extra pointers (two dummy nodes, two tail pointers, one traversal pointer). No arrays, no new data nodes.