Partition List
Problem Statement
Given the head of a linked list and a value x, partition the list so that all nodes with values less than x come before nodes with values greater than or equal to x. Preserve the original relative order of the nodes in each partition.
Input
The head of a singly linked list and an integer pivot x.
Output
The head of the partitioned list, with nodes less than x first and all other nodes after them.
Constraints
- •
0 <= number of nodes <= 200 - •
-100 <= Node.val <= 100 - •
-200 <= x <= 200
Examples
Example 1
head = 1 -> 4 -> 3 -> 2 -> 5 -> 2, x = 3
1 -> 2 -> 2 -> 4 -> 3 -> 5Example 2
head = 2 -> 1, x = 2
1 -> 2Example 3
head = 1 -> 1 -> 1, x = 5
1 -> 1 -> 1Learning Objectives
- Recognise stable partitioning as a two-dummy-bucket linked-list pattern.
- Append each node to exactly one tail while preserving relative order.
- Detach or terminate the greater-or-equal tail to avoid accidental cycles.
- Splice the less-than list before the greater-or-equal list in constant time.
Intuition
Pattern Recognition
The signal is partition while preserving relative order. If order did not matter, you might swap values or move nodes aggressively. Because stability matters, the clean linked-list pattern is two buckets: one list for nodes less than x, and one list for nodes greater than or equal to x.
Dummy heads remove edge cases. You do not need to know whether the first real node belongs to the less bucket or the greater-or-equal bucket. Each scanned node is appended to the correct tail, and tails always represent the end of their buckets.
The pointer trap is the original next links. If the greater-or-equal tail still points into the old list after splicing, the final list can contain stale nodes or even a cycle. Always terminate the final tail with null before returning.
Common mistakes
- ×Swapping node values, which does not demonstrate linked-list pointer control and can break identity-sensitive variants.
- ×Prepending nodes to a bucket, which reverses relative order and violates stability.
- ×Forgetting to connect the less-than tail to the greater-or-equal head at the end.
- ×Not setting the final tail's **next** to **null**, leaving stale links from the original list.
Algorithm Explanation
Key idea
Build two stable lists in one pass. lessTail always points to the last node with value less than x. greaterTail always points to the last node with value greater than or equal to x. Appending to tails preserves order inside each group, and the final splice puts the groups together.
Pointer walkthrough
For 1 -> 4 -> 3 -> 2 -> 5 -> 2 with x = 3, start with lessDummy and greaterDummy. Visit 1 and append it to the less bucket: lessDummy -> 1. Visit 4 and append it to the greater-or-equal bucket: greaterDummy -> 4. Visit 3, append after 4: greaterDummy -> 4 -> 3. Visit 2, append after 1: lessDummy -> 1 -> 2. Visit 5, append after 3. Visit the final 2, append after the less bucket's 2. Now splice lessTail.next to greaterDummy.next, producing 1 -> 2 -> 2 -> 4 -> 3 -> 5, and terminate the final greater tail.
Algorithm
- Create lessDummy and greaterDummy.
- Keep lessTail and greaterTail at the ends of those two lists.
- Walk the original list from head to null.
- Save nextNode before rewiring the current node.
- If current.val < x, append current after lessTail and advance lessTail.
- Otherwise append current after greaterTail and advance greaterTail.
- Terminate greaterTail.next with null, connect lessTail.next to greaterDummy.next, and return lessDummy.next.
Solutions
Solution: Two dummy buckets
Use this whenever a linked-list problem asks for a stable split into two groups and then a splice.
Create one dummy-headed list for nodes less than x and one for nodes greater than or equal to x. Append each original node to exactly one bucket, then connect the less bucket to the greater-or-equal bucket.
Step-by-step
- Initialise lessDummy, greaterDummy, lessTail, and greaterTail.
- Traverse with current and save nextNode before changing any links.
- Detach current.next so the node is clean before it joins a bucket.
- Append current to the less bucket if its value is below x; otherwise append it to the greater-or-equal bucket.
- Move current to nextNode and continue.
- Set greaterTail.next to null, connect lessTail.next to greaterDummy.next, and return lessDummy.next.
O(n)
O(1)
Each node is visited and relinked once; the two dummy nodes and tails are constant extra space.
Java implementation
Dry Run
Sample input
head = 1 -> 4 -> 3 -> 2 -> 5 -> 2, x = 3. Track the two buckets as each node is appended.
| node | comparison | less bucket | greater-or-equal bucket | action |
|---|---|---|---|---|
| 1 | 1 < 3 | 1 | empty | append to less |
| 4 | 4 >= 3 | 1 | 4 | append to greater-or-equal |
| 3 | 3 >= 3 | 1 | 4 -> 3 | append to greater-or-equal |
| 2 | 2 < 3 | 1 -> 2 | 4 -> 3 | append to less |
| 5 | 5 >= 3 | 1 -> 2 | 4 -> 3 -> 5 | append to greater-or-equal |
| 2 | 2 < 3 | 1 -> 2 -> 2 | 4 -> 3 -> 5 | append to less |
| splice | done | 1 -> 2 -> 2 | 4 -> 3 -> 5 | connect less tail to greater head |
Appending to bucket tails preserves order within both groups. After splicing, the final list is 1 -> 2 -> 2 -> 4 -> 3 -> 5.
Interview Tips
Say the word stable early. It explains why you append to tails instead of pushing to heads or swapping values. Draw the two dummy heads before coding; this removes the hardest edge cases. End by explicitly setting the final greater-or-equal tail to null, because interviewers often look for that stale-link bug.
Likely follow-ups
- How would you partition into three buckets: less than, equal to, and greater than **x**?
- What changes if nodes must be copied instead of relinked?
- How would you partition a doubly linked list while preserving both **next** and **prev** pointers?
- How would you make the partition unstable but possibly reduce pointer assignments?
Similar Problems
Key Takeaways
- Stable partitioning is easiest with two dummy-headed buckets.
- Appending to tails preserves the original relative order inside each bucket.
- Saving **nextNode** before rewiring prevents losing the rest of the original list.
- Always terminate the final tail to avoid stale links or cycles.