You are given head, the first node of a singly linked list, and an integer pivot. Rearrange the list so that every node with a value less than pivot comes before every node with a value greater than or equal to pivot.
Within each of the two groups, the nodes must keep their original relative order.
Return the head of the rearranged list.
Linked List Encoding
Your function receives head as a ListNode (or null for the empty list) and returns the head of the rearranged list. The node type is provided for you, with val and next fields.
The examples below write a list as the array of its values in order, so [1,2,3] is the list 1 -> 2 -> 3. That is only how lists are displayed; the encoding and decoding are done for you.
Examples
Example 1
Input: head = [1,4,3,2,5,2], pivot = 3
Output: [1,2,2,4,3,5]
Explanation: The values less than 3 are 1, 2, 2, in that order. The remaining values are 4, 3, 5, in that order. The first group comes first.
Example 2
Input: head = [2,1], pivot = 2
Output: [1,2]
Explanation: Only 1 is less than 2, so it moves to the front. The value 2 equals the pivot, so it belongs to the second group.
Constraints
The number of nodes in the list is in the range [0,200].
−100≤Node.val≤100
−200≤pivot≤200
Loading editor...
Run checks the sample cases; Submit runs every case.
Samples 2
Custom 0
passedwrong answertime limiterrorran, no expected valuenot run