564. Find the Closest Palindrome

class Solution {
    // Time: O(n), Space: O(n)
    public String nearestPalindromic(String n) {
        if (n == null || n.length() == 0) {
            return n;
        }

        int len = n.length();
        char[] tmp = n.toCharArray();
        int i=0;
        int j=len-1;
        while (i < j) {
            tmp[j] = tmp[i];
            i++;
            j--;
        }

        int midElem = tmp[(len-1)/2] - '0';
        long orig = Long.parseLong(n);
        long diff = Long.MAX_VALUE;
        long res = orig;

        for (int k=Math.min(9, midElem+1); k>=Math.max(0, midElem-1); k--) {
            if (len%2 == 0) {
                tmp[len/2] = (char) (k + '0');
            }
            tmp[(len-1)/2] = (char) (k + '0');
            long val = Long.parseLong(new String(tmp));
            if (val == orig) {
                continue;
            }
            if (diff >= Math.abs(orig - val)) {
                diff = Math.abs(orig - val);
                res = val;
            }
        }

        if (midElem == 0 || midElem == 1 || midElem == 9) {
            long val9 = 0;
            long val1 = 1;
            for (int k=0; k<len-1; k++) {
                val9 = val9*10 + 9;
                val1 = val1*10;
            }
            val1 = val1*10 + 1;

            if (orig != val9 && diff >= Math.abs(orig - val9)) {
                diff = Math.abs(orig - val9);
                res = val9;
            }

            if (orig != val1 && diff >= Math.abs(orig - val1)) {
                diff = Math.abs(orig - val1);
                res = val1;
            }
        }

        return String.valueOf(res);
    }
}