104. Wiggle Sort II

Given an integer array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3].... Return any valid wiggle permutation.

Input: Integer array nums.

Output: Array reordered in wiggle sort order (strictly alternating).

Examples

Example 1

Input: [1,5,1,1,6,4]
Output: [1,6,1,5,1,4]
Explanation: One valid output: [1,6,1,5,1,4]. Odd indices strictly greater than neighbors.

Example 2

Input: [1,3,2,2,3,1]
Output: [2,3,1,3,1,2]
Explanation: One valid output.

Example 3

Input: [1,2,3,4,5,6]
Output: [1,4,2,5,3,6]
Explanation: Even positions from smaller half, odd from larger half.