Масивите за четни и нечетни ги правиш по голями - определено броя на четните и нечетните числа не са равни на броя на всичките числа, с изключение когато всичките са четни или нечетни - както сам си забелязал. По този начин имаш 0-ли в клетките които са в повече!

Edit: Ето и примерно решение на проблема

1. int oddCount = 0;
3. for (int i = 0; i< digits.length; i++) {
4.         if (digits[i]%2==1) {
5.                 oddCount++;
6.         } 
7. }
9. int[] oddNums = new int[oddCount];
10. int[] evenNums = new int[digits.length - oddCount];
12. oddCount = 0;
13. int evenCount = 0;
15. for (int i = 0; i< digits.length; i++) {
16.        if (digits[i]%2==1) {
17.                oddNums[++oddCount] = digits[i];
18.        } else {
19.                evenNums[++evenCount] = digits[i];
20.        }                       
21. }