Skills101
← All coding problems

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).

Loading editor…

Log in to run and submit your code — it's free.