Odd-Even Linked List Rearrangement

Given a singly linked list, rearrange the nodes such that all nodes at odd positions are listed before nodes at even positions. The positions refer to the node indices in the original list starting from 1. For example, given a list: (1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5), the rearranged list becomes: (1 \rightarrow 3 \rightarrow 5 \rightarrow 2 \rightarrow 4).

The task is to implement this rearrangement with a time complexity of (O(n)) and constant space complexity (O(1)) (excluding the space used by the input).

inputFormat

The input is given via standard input (stdin). The first line contains an integer (n) representing the number of nodes in the linked list. The second line contains (n) space-separated integers, which are the values of the nodes.

outputFormat

Print the values of the rearranged linked list via standard output (stdout) as space-separated integers in one line.## sample

5
1 2 3 4 5

1 3 5 2 4