剑指offer：调整数组顺序使奇数位于偶数前面

题目分析

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
这里提供一个解法，时间复杂度为O(n)，空间复杂度为O(n)。

代码

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public void reOrderArray(int [] array) {
        // 题目要求前半部分为奇数，后半部分为偶数
        List<Integer> odd = new ArrayList<>();
        List<Integer> even = new ArrayList<>();
        for(int i = 0; i < array.length; i++) {
            if(array[i] % 2 == 0) {
                even.add(array[i]);
            } else {
                odd.add(array[i]);
            }
        }
        int k = 0;
        for(int i = 0; i < odd.size(); i++) {
            array[k++] = odd.get(i);
        }
        for(int i = 0; i < even.size(); i++) {
            array[k++] = even.get(i);
        }
    }
}