410. Reorder List to Min-Max Interleaving

Given a linked list, reorder it so the values follow a min-max interleaving: smallest, largest, second smallest, second largest, and so on. This is achieved by sorting the values and then alternately taking from the front and back. Return the resulting list as an array.

Input: An array of node values.

Output: Array — the min-max interleaved list.

Examples

Input: [1,2,3,4,5,6]
Output: [1,6,2,5,3,4]
Explanation: Alternate smallest and largest.

Input: [5,4,3,2,1]
Output: [1,5,2,4,3]
Explanation: Sorted then interleaved.

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

Constraints

• 0<=n<=10^5
• -10^9<=value<=10^9

Asked by