324. Wiggle Sort II

Given an integer array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]….

You may assume the input array always has a valid answer.

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        if(nums.size() <= 2) {
            sort(nums.begin(), nums.end());
            return ;
        }
        vector<int> sorted(nums.begin(), nums.end());
        sort(sorted.begin(), sorted.end());
        int tail = nums.size() - 1, head = tail>>1, pos = 0;
        while(head >= 0) {
            nums[pos++] = sorted[head--];
            if(tail >= nums.size()/2)
                nums[pos++] = sorted[tail--];
        }
    }
};