Given the head of a singly linked list and an integer 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. Inside each of the two groups the nodes must keep their original relative order. Return the head.
Examples
Input: head = 1 -> 4 -> 3 -> 2 -> 5 -> 2, x = 3
Output: 1 -> 2 -> 2 -> 4 -> 3 -> 5
Input: head = 2 -> 1, x = 2
Output: 1 -> 2
Constraints
0 <= number of nodes <= 10**4- Target: O(n) time, O(1) extra space, one pass; relink nodes rather than copying values
Goals
- Distribute nodes into two chains and join them
- Preserve the original relative order inside each group