Partition List

Medium

Given the head of a linked list and a value k, partition it so that all nodes with value less than k come before nodes with value greater than or equal to k. Preserve the original relative order within each part. (LeetCode calls this parameter x.)

Example 1

Input:  head = [1,4,3,2,5,2], k = 3
Output: [1,2,2,4,3,5]

Example 2

Input:  head = [2,1], k = 2
Output: [1,2]

Constraints

• 0 <= number of nodes <= 200
• -100 <= Node.val <= 100
• -200 <= k <= 200