Partition 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

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]. Nodes ≥ 3: [4,3,5]. Concatenated: [1,2,2,4,3,5].

Example 2:

Input: head = [2,1], x = 2

Output: [1,2]

Explanation: Node less than 2: [1]. Nodes ≥ 2: [2]. Concatenated: [1,2].

Example 3:

Input: head = [1,2,3], x = 4

Output: [1,2,3]

Explanation: All nodes are less than 4, so the list is unchanged.

Constraints

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