Partition List
Given the head of a linked list and a value x, partition it so that all nodes with values less than x come before nodes with values greater than or equal to x, preserving the original relative order within each partition.
- The number of nodes in the list is in the range [0, 200].
- -100 <= Node.val <= 100
- -200 <= x <= 200
Intuition
Partition list reorders a linked list so all nodes with values below x come before those at or above it, preserving the relative order within each group. That stability requirement rules out the swapping tricks that would otherwise work.
Swapping nodes or values to move small elements forward would destroy the original ordering. The approach that preserves it builds two separate chains:
- Walk the list once, appending each node to a "less than" chain or a "greater or equal" chain, then join the two.
Because nodes are appended in the order encountered, the relative order within each group is preserved automatically — no extra work is needed to maintain it.
Two dummy heads, one per chain, remove all the special-casing. Without them, each append needs a branch to distinguish the first node from the rest, doubling the code.
The step that cannot be skipped is terminating the second chain. Setting greaterTail.next = null before joining is essential: the last node of that chain may still point into the original list, and without the termination the result contains a cycle and any traversal loops forever.
That is the defining bug of this problem, and it often passes small tests where the final node happens to be the list's tail.
Joining is then lessTail.next = greaterDummy.next, and the answer is lessDummy.next.
The case where one group is empty needs no handling — the dummy's next is null, so joining an empty chain works correctly on its own.
One pass relinking pointers gives O(n) time and O(1) space, with no node allocation beyond the two dummies.
When a linked list problem asks you to reorder nodes based on a condition while preserving relative order within each group, the pattern is: build separate sub-lists with dummy heads, route each node, then stitch. This avoids complex in-place pointer surgery and keeps the logic linear and clear.
Approach
Before reading on: price up what the direct approach costs here, then ask which pointers must be saved before you overwrite anything. Aim for O(n) time and O(1) space.
Rule out swapping
Swapping nodes or values destroys the relative order, which the problem requires preserving. Two separate chains keep it intact for free.
Build two chains
Walk the list once, appending each node to a less-than chain or a greater-or-equal chain. Nodes join in the order encountered, preserving stability.
Use two dummy heads
A dummy per chain removes the branch that would otherwise distinguish the first append from every later one.
Terminate the second chain
Set the greater chain's tail next to null before joining. Its last node may still point into the original list, creating a cycle — the defining bug here.
Join the chains
Set lessTail.next = greaterDummy.next and return lessDummy.next. An empty group needs no special case, since the dummy's next is already null.
Cost of the approach
One pass relinking pointers gives O(n) time and O(1) space, allocating only the two dummy nodes.
Solution & live demo
Common pitfalls
Forgetting to set geq_tail.next = None to avoid a cycle
less_tail.next = geq_dummy.next return less_dummy.next
geq_tail.next = None less_tail.next = geq_dummy.next return less_dummy.next
The last node in the geq partition still has its old .next pointer, which may point back into the less partition. Without nullifying it, the list has a cycle and traversal loops forever.
Using >= instead of < for the less partition check
if node.val <= x:
less_tail.next = nodeif node.val < x:
less_tail.next = nodeNodes equal to x should go in the geq partition, not the less partition. Using <= pulls x-valued nodes into the wrong group, changing the output order.
Not advancing the original head pointer during traversal
while head:
if head.val < x:
less_tail.next = head
less_tail = less_tail.next
head = head.nextwhile head:
if head.val < x:
less_tail.next = head
less_tail = less_tail.next
else:
geq_tail.next = head
geq_tail = geq_tail.next
head = head.nextForgetting the else branch drops all geq nodes. They are never appended to the geq sub-list and are lost.
Edge cases
xThe geq sub-list is empty. less_tail.next = geq_dummy.next = None, so the list is just the less partition.
xThe less sub-list is empty. less_dummy.next = geq_dummy.next, returning the geq partition directly.
The loop does not run. less_dummy.next is None. Correct.