**Solution**

**Wiggle Sort** https://leetcode.com/problems/wiggle-sort/

**Solution 1: Sorting**

- Just sort the array and swap adjacent elements

```
class Solution(object):
def wiggleSort(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
nums.sort()
i = 1
while i+1 < len(nums):
nums[i], nums[i+1] = nums[i+1], nums[i]
i += 2
return
```

**Solution 2: O(N) solution in one pass**

- Assume a1,a2,..a[n-1],a[n] is already wiggle sorted.
- Now we have a[n+1] and we want a[n]<=a[n+1]. This means a[n-1] >=a[n]
- Case 1: a[n] <= a[n+1] - All conditions are satisfied
- Case 2: a[n] > a[n+1]
- Swap and this leads to a[n-1] ? a[n+1] < a[n]
- What is ?. a[n-1] >=a[n]. a[n] > a[n+1]. This means a[n-1]>a[n+1]
- Hence we have a[n-1] > a[n+1] < a[n]

```
class Solution(object):
def wiggleSort(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
i, less = 0, True
while i+1 < len(nums):
if less:
if nums[i+1] < nums[i]:
nums[i],nums[i+1] = nums[i+1], nums[i]
else:
if nums[i+1] > nums[i]:
nums[i],nums[i+1] = nums[i+1], nums[i]
i, less = i+1, not less
return
```