Reorder Linked List: Even Values First

You are given a singly linked list. Your task is to reorder the linked list so that all nodes with even values appear before all nodes with odd values while preserving the relative order of even nodes and odd nodes. In other words, if the list is represented as \(L = [l_1, l_2, \dots, l_n]\), then after reordering, all \(l_i\)'s that are even should appear before the odd ones, and the relative order among even and also among odd nodes must be the same as in \(L\).

Example:

Input: 8
       2 1 3 5 6 4 7 8
Output: 2 6 4 8 1 3 5 7

Note: The first number in the input denotes the number of nodes in the linked list, followed by the node values.

inputFormat

The input is given via standard input, and consists of two lines:

1. The first line contains a single integer \(n\) representing the number of nodes in the linked list. \(n\) can be zero.
2. The second line contains \(n\) space-separated integers representing the node values.

outputFormat

Output a single line via standard output containing the reordered linked list. The node values should be printed as space-separated integers.

8
2 1 3 5 6 4 7 8

2 6 4 8 1 3 5 7