Segregate Even and Odd Nodes in a Linked List

You are given a singly linked list containing integers. Your task is to rearrange the linked list so that all nodes containing even integers come before nodes containing odd integers. The relative order among the even nodes and among the odd nodes should remain unchanged from the original list.

Note: If the linked list is empty, simply output an empty list.

Mathematically, if the original linked list is represented as a sequence \(a_1,a_2,\dots,a_n\), where a node is even if \(a_i \mod 2 = 0\) and odd otherwise, then your program should output the sequence \(\{a_i \mid a_i \mod 2 = 0\}\) followed by \(\{a_j \mid a_j \mod 2 \neq 0\}\) preserving the initial order in each partition.

inputFormat

The input is read from standard input (stdin) and is formatted as follows:

• The first line contains an integer n representing the number of elements in the linked list.
• The second line contains n space-separated integers representing the values of the nodes in the linked list.

For example:

6
1 2 3 4 5 6

outputFormat

The output should be written to standard output (stdout) as a single line of space-separated integers representing the rearranged linked list where all even values appear before odd values, with the original order preserved within each group.

For example, the output for the sample input above would be:

2 4 6 1 3 5

## sample

6
1 2 3 4 5 6

2 4 6 1 3 5