Odd Even Linked List
mediumLinked List & Stack II+20 XPTime limit 2s
Number the nodes of a linked list 1, 2, 3, … from the head. Rearrange the list so that all odd-numbered nodes come first, followed by all even-numbered nodes. Inside each group, keep the original order. (It is about the node positions, not their values.)
List format. A linked list is given as two lines: its length n, then its n values from head to tail (the second line is empty when n = 0). When you print a list, print its values on one line separated by spaces, or the word empty if it has no nodes.
Input: one list.
Output: the rearranged list.
Constraints: 0 ≤ n ≤ 10⁵, −1000 ≤ value ≤ 1000.
Challenge: do it in place with O(1) extra memory: keep an odd tail and an even tail, hop each one two nodes forward, and finally attach the head of the even chain after the last odd node.
Sample input 1
5 1 2 3 4 5
Sample output 1
1 3 5 2 4
Sample input 2
7 2 1 3 5 6 4 7
Sample output 2
2 3 6 7 1 5 4
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).