86. Partition List
You receive the head of a singly linked list and an integer x. Rearrange the nodes so that every node holding a value strictly less than x appears before every node holding a value greater than or equal to x, then return the head of the rearranged list.
The split must be stable: within each of the two groups, nodes keep the relative order they had in the original list. Nodes whose value equals x belong to the second group.
An empty list simply stays empty.
Example 1:
Input: head = [1, 4, 3, 2, 5, 2], x = 3
Output: [1, 2, 2, 4, 3, 5]
Explanation: Values below 3 are 1, 2, 2 (in original order); the rest are 4, 3, 5 (also in original order). The first group leads, the second follows.
Example 2:
Input: head = [2, 1], x = 2
Output: [1, 2]
Explanation: Only 1 is strictly below 2, so it moves to the front. The node equal to x stays in the second group.
Constraints:
- 0 ≤ number of nodes ≤ 200
- -100 ≤ node value ≤ 100
- -200 ≤ x ≤ 200
Hints:
No node is ever compared with another node — each one is judged against `x` alone. That means a single left-to-right walk can decide every node's group immediately.
Grow two separate chains from two dummy heads: one collects nodes below `x`, the other collects everything else. Appending in scan order makes stability automatic; at the end, stitch the first chain's tail to the second chain's head and null-terminate the second tail.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: head = [1, 4, 3, 2, 5, 2], x = 3
Expected output: [1, 2, 2, 4, 3, 5]