The basic idea is to first select the kth smallest element, where k is the half the size (if size is even) or half the size+1 (if size is odd). So the array is partitioned into two halves, for even size, left half size==right half size, for odd size, left half size==right half size+1. Then iterate back from left and right half, put each value into original array.
For example, [1, 5, 1, 1, 6, 4], after select kth smallest element, it becomes [1,1,1,5,6,4] with median index of 2. For the left half is [1,1,1], right half is [5,6,4]. After merge, it becomes, 1,4,1,6,1,5.
Same for [4,5,5,6], after select kth smallest , it becomes [4,5,5,6] with left half [4,5] and right half [5,6], merge it to be [5,6,4,5].
The tricky parts:

Do a threewaypartition, so that the duplicates are around median, so that they can be split

Iterate from the back of two halves, so that the duplicates in between can be split apart.
public class Solution {
public void wiggleSort(int[] nums) {
int median = selectKth(nums, 0, nums.length1, nums.length%2==0 ? nums.length/2 : nums.length/2+1);
List<Integer> leftArr = new ArrayList<Integer>();
for(int i=0; i<=median; i++)
leftArr.add(nums[i]);
List<Integer> rightArr = new ArrayList<Integer>();
for(int i=median+1; i<nums.length; i++)
rightArr.add(nums[i]);
for(int li=leftArr.size()1,ri=rightArr.size()1,i=0; ri>=0; li,ri,i+=2) { // right is same or shorter than left
nums[i] = leftArr.get(li);
nums[i+1] = rightArr.get(ri);
}
if(nums.length%2!=0)
nums[nums.length1] = leftArr.get(0);
}private int selectKth(int[] nums, int start, int end, int k) { int[] res = partition(nums,start,end); int lb = res[0]; int hb = res[1]; if(k1<lb) return selectKth(nums,start,lb1,k); else if (k1>hb) return selectKth(nums,hb+1,end,k); else return k1; } private int[] partition(int[] nums, int lb, int hb) { int pVal = nums[lb]; // use random genarater is better in performance int i = lb; while(i<=hb) { if(nums[i]==pVal) i++; else if(nums[i]<pVal) swap(nums,i++,lb++); else swap(nums,i,hb); } int[] res = new int[2]; res[0] = lb; res[1] = hb; return res; } private void swap(int[] nums, int i, int j) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; }
}