Java перестановка с чередованием чётности

Использовал LinkedList для удобства (в строчке ints.addFirst(ints.removeLast())).
Решил, что лучше будет использовать Map.Entry.

static Map.Entry<LinkedList<Integer>,Integer> solve(LinkedList<Integer> ints) {
    int num = 0;
    if(ints.size() > 0) {
        boolean lastNumOdd = (ints.getFirst() & 1) == 1;
        for (int i = 1; i < ints.size(); i++) {
            boolean oldLastNumOld = lastNumOdd;
            lastNumOdd = (ints.get(i) & 1) == 1;
            if(lastNumOdd == oldLastNumOld) {
                if(i == ints.size() - 1)
                    ints.addFirst(ints.removeLast());
                else {
                    for (int j = i + 1; j < ints.size(); j++)
                        if(lastNumOdd ? (ints.get(j) & 1) == 0 : (ints.get(j) & 1) == 1) {
                            int tmp = ints.get(j);
                            ints.set(j, ints.get(i));
                            ints.set(i, tmp);
                            break;
                        }
                    lastNumOdd = (ints.get(i) & 1) == 1;
                }
                num++;
            }
        }
    }
    final int finalNum = num;
    return new Map.Entry<>() {
        public LinkedList<Integer> getKey() { return ints; }
        public Integer getValue() { return finalNum; }
        public Integer setValue(Integer value) { return null; }
    };
}

Когда два элемента подряд идут одной чётности, проверяем, конец ли это списка. Если да, то вставляем в начало последний элемент, если нет, то ищем элемент другой чётности и вставляем его на место последнего проверенного нами.

Подразумевается, что количество чётных и нечётных чисел отличается на 1. Если входные данные могут быть другими, необходимо сделать в начале метода проверку.

int oddNum = 0, evenNum = 0;
for (int i : ints) if((i & 1) == 1) oddNum++; else evenNum++;
if(Math.abs(oddNum - evenNum) > 1) throw new IllegalArgumentException();

Хотя лучше будет сделать проверку в блоке if(i == ints.size() - 1).

if(i == ints.size() - 1) {
    ints.addFirst(ints.removeLast());
    if(lastNumOdd == ((ints.get(1) & 1) == 1))
        throw new IllegalArgumentException();
}