Although a worst case O(n) solution is available, it would make it too challenging to write during an interview. The function nth_element in C++ is readily available and is expected to have O(n) time complexity on average. Need some help, though, on how to make space complexity to be O(1).

The algorithm is relatively straight-forward following the proof given by StefanPochmann in

https://leetcode.com/discuss/76965/3-lines-python-with-explanation-proof

```
class Solution {
public:
void wiggleSort(vector<int>& nums) {
int n = nums.size();
int mid = n/2;
nth_element(nums.begin(), nums.begin() + mid, nums.end());
threeWayPartition(nums, nums[mid]);
vector<int> res(n);
int largeStart = n-1;
int smallStart = (n%2) ? mid : (mid-1);
for (int i = 0; i < n; i+=2)
res[i] = nums[smallStart--];
for (int i = 1; i < n; i+=2)
res[i] = nums[largeStart--];
nums = res;
}
// this ensures all values equal to the median is in the middle
void threeWayPartition(vector<int> &nums, int val) {
int i = 0, j = 0;
int n = nums.size()-1;
while (j <= n){
if (nums[j] < val)
swap(nums[i++], nums[j++]);
else if (nums[j] > val)
swap(nums[j], nums[n--]);
else
j++;
}
}
};
```