DSA problem
Partition List
Given the head of a linked list and a value x, partition the list so that all nodes with a value strictly less than x come before all nodes with a value greater than or equal to x. The crucial requirement is that you must preserve the original relative order of the nodes within each of the two partitions.
This is essentially the partition step of a stable sort applied to a linked list. Because the ordering within each group must be maintained, you cannot simply swap nodes around arbitrarily; a value-comparison-based bubbling would also be unstable and slow.
Rather than mutating values in place, the cleanest technique splits the original list into two independent sublists during a single traversal. One sublist collects every node whose value is less than x, and the other collects every node whose value is greater than or equal to x.
The intuition is to maintain two dummy-headed lists, a less list and a greater list. As we scan the original list once, we append each node to the tail of the appropriate list. At the end, we concatenate the less list with the greater list and crucially terminate the greater list's tail with null to avoid a cycle. This gives a stable partition in O(n) time and O(1) extra space.
Examples
head = [1,4,3,2,5,2], x = 3[1,2,2,4,3,5]head = [2,1], x = 2[1,2]head = [], x = 0[]Constraints
- The number of nodes in the list is in the range [0, 200].
- -100 <= Node.val <= 100
- -200 <= x <= 200
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.