1
class Solution {
2
  public int[] sortArrayByParityII(int[] A) {
3
    int i = 0, j = 1, n = A.length;
4
    while (i < n && j < n) {
5
      while (i < n && A[i] % 2 == 0) {
6
        i += 2;
7
      }
8
      while (j < n && A[j] % 2 == 1) {
9
        j += 2;
10
      }
11
      if (i < n && j < n) {
12
        swap(A, i, j);
13
      }
14
    }
15
    return A;
16
  }
17

18
  private void swap(int[] A, int i, int j) {
19
    int temp = A[i];
20
    A[i] = A[j];
21
    A[j] = temp;
22
  }
23
}