Partition List
Medium · Linked Lists · Linked List · Two Pointers
Problem
Given the head of a linked list and a value x, rearrange the nodes so that every node with a value less than x comes before every node with a value greater than or equal to x.
Within each of the two groups, keep the nodes in their original relative order. Return the head of the rearranged list.
Examples
Input: head = [5,1,4,2,6,3], x = 4 Output: [1,2,3,5,4,6]
1, 2 and 3 are below 4 and move ahead of 5, 4 and 6; both groups keep their order.
Input: head = [2,1], x = 2 Output: [1,2]
Only 1 is smaller than 2.
Input: head = [], x = 0 Output: []
There are no nodes to move.
Constraints
- The list has between 0 and 200 nodes
- -100 <= Node.val <= 100
- -200 <= x <= 200
Approaches
- Baseline: copy the nodes into an array and relink — time O(n), space O(n)
Follow-up
Two chains joined at the end is a stable partition in O(1) extra space. The use cases ask the same thing of arrays, and split into three groups instead of two.
Related problems
Start free on Cariara · Coding problems · System design studio
