360. Reorder List

Given a singly linked list L0 -> L1 -> ... -> Ln-1 -> Ln, reorder it to L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> ... You may not modify the values, only the node links. The list is given as an array; return the reordered array.

Input: An array of node values.

Output: Array — the reordered list.

Examples

Input: [1,2,3,4]
Output: [1,4,2,3]
Explanation: Front and back interleaved.

Input: [1,2,3,4,5]
Output: [1,5,2,4,3]
Explanation: Odd length keeps the middle last.

Input: [1]
Output: [1]
Explanation: Single node.

Constraints

• 1<=n<=5*10^4
• -10^5<=value<=10^5

Asked by