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.
Intuition
Think of it as building two separate linked lists — one for nodes less than x, one for nodes >= x — and then stitching them together. You do not need to move nodes in place or swap values. Walk through the original list once, appending each node to the appropriate sub-list. When done, connect the tail of the 'less' list to the head of the 'greater-or-equal' list. Dummy heads on both sub-lists eliminate all edge-case branching for empty partitions.
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
Create two dummy-headed sub-lists for the two partitions
Allocate two dummy nodes: less_dummy for nodes with val < x, and geq_dummy for nodes with val >= x. Maintain tail pointers less_tail and geq_tail for appending. Dummy heads mean you never have to check whether the sub-list is empty before appending.
Walk the original list and route each node
For each node, compare its value to x. If less, append to less_tail and advance less_tail. Otherwise, append to geq_tail and advance geq_tail. Advance head to the next node. After the loop, every node has been moved to one of the two sub-lists.
Stitch the two sub-lists and terminate
Set less_tail.next = geq_dummy.next to connect the less partition to the greater-or-equal partition. Crucially, set geq_tail.next = None to terminate the list — without this, the last node in the geq partition still points to its old successor, creating a cycle. Return less_dummy.next.
Solution
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.