Arrange Odd and Even Nodes in a Linked List

You are given a singly linked list where each node contains an integer. Your task is to rearrange the list so that all nodes with odd integer values appear before nodes with even integer values, while preserving the relative order among the odd nodes and even nodes.

Construct the linked list from the input and then output the rearranged list. If the list is empty, output nothing.

Note: The term "odd" and "even" refer to the integer values stored inside the nodes, not their positions in the list.

inputFormat

The input consists of two lines:

• The first line contains a single integer n, the number of nodes in the linked list.
• The second line contains n integers separated by spaces, which represent the values of the nodes.

outputFormat

Output a single line containing the rearranged linked list's node values separated by spaces. The order is such that all odd-valued nodes appear first, followed by all even-valued nodes, each preserving their original relative order.

5
1 2 3 4 5

1 3 5 2 4