Partition a List Around a Value
Stably rearrange a linked list so every node less than a pivot value comes before every node greater than or equal to it.
Given the head of a singly-linked list and a value x, partition the list so that every node with a value less than x appears before every node with a value greater than or equal to x.
You must preserve the original relative order of the nodes within each of the two partitions -- this is a stable partition, not a sort.
Return the values of the partitioned list.
Example 1
Input: head = [1,4,3,2,5,2], x = 3
Output: [1,2,2,4,3,5]
Explanation: Nodes less than 3 (1, 2, 2) keep their relative order and come first, followed by nodes >= 3 (4, 3, 5) in their original relative order.
Example 2
Input: head = [2,1], x = 2
Output: [1,2]
Example 3
Input: head = [], x = 5
Output: []
Constraints
- The number of nodes in the list is in the range [0, 200].
- -100 <= Node.val <= 100
- -100 <= x <= 100
Follow-up
Can you solve it using only two extra pointers (one for the tail of each partition) and a single pass through the list, without allocating any new nodes?
Hints
Companies
No companies reported yet.
Discussion
Sign in to join the discussion.
Loading discussion...
Test results
No test cases yet.