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.

Class Node:
    data (int)
    next (Node)

Input Format:

First Parameter - Node head

Second Parameter - Number x

Output Format:

Return the Node.

Example 1:

Input:
    1 4 3 2 5 2
    3
Output:
    1 2 2 4 3 5

Example 2:

Input:
    2 1
    2
Output:
    1 2

Constraints:

• 1<= No. of nodes in either list <=10⁴
• -100 <= Node.data <=100
• -200 <= X <= 200
• Expected Time Complexity: O(n)
• Expected Auxiliary Space: O(1)