81. Partition List

MediumLinked List

Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x. You should preserve the original relative order of the nodes in each of the two partitions.

Examples

Input: [1,4,3,2,5,2] 3

Output: [1,2,2,4,3,5]

Explanation: Nodes < 3 (1,2,2) keep order and come first; the rest (4,3,5) follow in order.

Constraints

The number of nodes in the list is in the range [0, 200].
-100 <= Node.val <= 100
-200 <= x <= 200

Run checks all cases above. Submit evaluates all test cases.