Четность соседей

import java.util.*;
public class Even {
public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    int[] A = new int[n];
    int evenCount = 0;
    int oddCount = 0;
    for (int i = 0; i < n; i++) {
        int nextInt = scanner.nextInt();
        A[i] = nextInt;
        if (nextInt % 2 == 0) { 
            evenCount++;
        } else {
            oddCount++;
        }
    }
    scanner.close();
    if (Math.abs(evenCount - oddCount) > 1) {
        System.out.println(-1);
        return;
    } else if (evenCount == 0 || oddCount == 0) {
        System.out.println(0);
        System.out.print(A[0]);
        return;
    } else {
        int[] B = A.clone();
        if (evenCount > oddCount) {
            if ((A[0] % 2) != 0) {
                int temp = A[0];
                for (int i = 1; i < n; i++) {
                    if ((A[i] % 2) == 0) {
                        A[0] = A[i];
                        A[i] = temp;
                        break;
                    }
                }
            }
        } else if (evenCount < oddCount) {
            if ((A[0] % 2) == 0) {
                int temp = A[0];
                for (int i = 1; i < n; i++) {
                    if ((A[i] % 2) != 0) {
                        A[0] = A[i];
                        A[i] = temp;
                        break;
                    }
                }
            }
        }
        int k = 0;
        if (A[0] != B[0]) {
            k++;
        }
        int left = 0;
        for (int right = 1; right < n; right++) {
            if ((A[left] % 2) == (A[right] % 2)) {
                int temp = A[right];
                for (int position = right; position < n; position++) {
                    if ((A[position] % 2) != (A[left] % 2)) {
                        A[right] = A[position];
                        A[position] = temp;
                        break;
                    }
                }
            }
            if (A[right] != B[right]) {
                k++;
            }
            left++;
        }
        System.out.println(k);
        for (int i = 0; i < n; i++) {
            System.out.print(A[i] + " ");
        }
    }
}

Решал я как-то эту задачу для прохождения стажировки в Яндекс

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
public class Main {
    public static void main(String[] args) {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        try{
            int countNumbers = Integer.parseInt(reader.readLine());
            int countEvenNumbers = 0;  //Кол-во четных
            int countOddNumbers = 0;  //Кол-во нечетных
            int countNumbersInTheirPlacesEven = 0;  //количество чисел на своих местах для первого числа четного
            int countNumbersInTheirPlacesOdd = 0;


            String[] texts = reader.readLine().split(" ");
            int[] numbers = new int[texts.length];
            for(int i = 0; i < texts.length; i++){
                int number = Integer.parseInt(texts[i]);
                numbers[i] = number;
                Boolean isEven = number % 2 == 0;
                if((i % 2 == 0) == isEven){
                    countNumbersInTheirPlacesEven++;
                }
                else{
                    countNumbersInTheirPlacesOdd++;
                }
                if(isEven)
                    countEvenNumbers++;
                else
                    countOddNumbers++;
            }
            if(Math.abs(countEvenNumbers  - countOddNumbers) > 1){
                System.out.println(-1);
                return;
            }
            Boolean firstIsNumberOdd = countOddNumbers == countEvenNumbers ?
                    countNumbersInTheirPlacesOdd > countNumbersInTheirPlacesEven :
                    countOddNumbers > countEvenNumbers;

            Rearrange(numbers, firstIsNumberOdd);
        }
        catch (Exception e){
            System.out.println(e);
        }
    }
    private static void Rearrange(int[] numbers, Boolean firstIsOddNumber) {
        Stack<Integer> placeOddNumber = new Stack<Integer>();  //нечетные числа не на своих местах
        Stack<Integer> placeEvenNumber = new Stack<Integer>();

        for (int i = 0; i < numbers.length; i++) {
            if ((i % 2 == numbers[i] % 2) ^ !firstIsOddNumber) {   //если число не на своем месте
                if (numbers[i] % 2 == 1)
                    placeOddNumber.push(numbers[i]);
                else
                    placeEvenNumber.push(numbers[i]);
            }
        }
        int count = placeEvenNumber.size() + placeOddNumber.size();
        for (int i = 0; i < numbers.length; i++) {
            if ((i % 2 == numbers[i] % 2) ^ !firstIsOddNumber) {
                if (numbers[i] % 2 == 1)
                    numbers[i] = placeEvenNumber.pop();
                else
                    numbers[i] = placeOddNumber.pop();
            }
        }

        System.out.println(count);
        StringBuilder stringBuilder = new StringBuilder();
        for (int number: numbers) {
            stringBuilder.append(number + " ");
        }
        System.out.println(stringBuilder);

Что-то сильно намудрено. Разложите все элементы на две группы - четные и нечетные. А потом соберите их обратно через один, начав с тех, которых больше. Получившийся массив сравните с исходным, чтобы посчитать k. Для экономии места собирать можно в исходный массив, подсчитывая k на ходу.

Сделать так, как предлагает @Igor, не получится. Пример:

6
1 3 5 2 2 2

Раскладываем на две группы:

1 3 5
2 2 2

Собираем обратно:

1 2 3 2 5 2

Сравним с исходным:

1 3 5 2 2 2
1 2 3 2 5 2
- * * - * -

Получилось 3 отличия, тогда как на самом деле их должно быть два:

1 3 5 2 2 2 // оригинал
1 2 5 3 2 2 // меняем 3 с первой 2
1 2 5 2 3 2 // меняем 3 со второй 2
- * - - * - // два отличия