382. Rearrange Linked List to Alternating Low-High

Rearrange a linked list so the values alternate low, high, low, high — that is, the result satisfies a[0] <= a[1] >= a[2] <= a[3] >= ... Return a canonical valid arrangement obtained by sorting the values and then swapping each adjacent pair starting at index 1. Return the result as an array.

Input: An array of node values.

Output: Array — the alternating arrangement.

Examples

Input: [1,2,3,4,5,6]
Output: [1,3,2,5,4,6]
Explanation: Sorted then adjacent pairs swapped from index 1.

Input: [3,1,2]
Output: [1,3,2]
Explanation: 1<=3>=2.

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

Constraints

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

Asked by