Rearrange Odd and Even Indexed Nodes in a Linked List

Given a singly linked list, your task is to rearrange it so that all nodes originally at odd-numbered positions (i.e. positions 0, 2, 4, … when indexed from 0) come before all nodes originally at even-numbered positions (i.e. positions 1, 3, 5, …). The relative order of the nodes in each group must be preserved. This should be accomplished in one pass with an optimal time complexity of $O(n)$ and constant extra space.

For example, if the input linked list is:

1 2 3 4 5

The rearranged linked list is:

1 3 5 2 4.

inputFormat

Input is given as a single line of space-separated integers representing the values of the nodes in the linked list. There will be at least one integer.

outputFormat

Output a single line of space-separated integers which represent the rearranged linked list after grouping the nodes at odd-index positions (0-indexed) first, followed by the nodes at even-index positions.## sample

1 2 3 4 5

1 3 5 2 4