Partition Linked List

You are given a singly linked list and an integer x. Your task is to partition the linked list such that all nodes with values less than x come before nodes with values greater than or equal to x. The relative order of nodes in each partition must be preserved.

Detailed Explanation:

• The linked list is provided in the form of n nodes.
• You are also given an integer x that will be used as the partitioning value.
• Your solution should create two separate partitions — one for nodes with values less than $$x$$ and one for nodes with values greater than or equal to $$x$$. After partitioning, concatenate the two lists so that the less-than-$$x$$ partition comes first.

For example, consider the linked list 1 -> 4 -> 3 -> 2 -> 5 -> 2 with x = 3. The output should be 1 -> 2 -> 2 -> 4 -> 3 -> 5 because all nodes with values less than 3 come before nodes with values greater than or equal to 3, while retaining their original relative order.

inputFormat

The input is read from standard input (stdin) and consists of the following:

1. An integer n representing the number of nodes in the linked list.
2. A line with n space-separated integers representing the node values. If n is 0, this line will be empty.
3. An integer x which is the partition value.

For example:

6
1 4 3 2 5 2
3

outputFormat

Output to standard output (stdout) the partitioned linked list as a single line of space-separated integers. If the resulting linked list is empty, output an empty line.

For example, for the input above, the output should be:

1 2 2 4 3 5

## sample

6
1 4 3 2 5 2
3

1 2 2 4 3 5