Rearrange the integers in nums into a zigzag order: a new list z (a permutation of nums) such that
z[0] <= z[1] >= z[2] <= z[3] >= z[4] ...
Any arrangement satisfying the pattern is accepted. Return a new list; do not modify the input.
Examples
Input: nums = [3, 5, 2, 1, 6, 4]
Output: [1, 3, 2, 5, 4, 6] (one of several valid answers)
Explanation: 1 <= 3 >= 2 <= 5 >= 4 <= 6.
Constraints
0 <= len(nums) <= 5 * 10**4- Duplicates are allowed; equal neighbours satisfy both
<=and>=. - Target complexity: O(n log n) (an O(n) single pass also exists).
Goals
- Produce an arrangement that satisfies an alternating inequality pattern
- Use a sorted order as a stepping stone to a non-standard order
- Accept that many outputs are valid and reason about correctness, not a single answer