Problem

Determine whether an integer is a palindrome. Do this without extra space.

click to show spoilers.

Some hints:
Could negative integers be palindromes? (ie, -1)
NO

If you are thinking of converting the integer to string, note the restriction of using extra space.

You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?

There is a more generic way of solving this problem.

Note

逐位看官，这两种解法一看便知，小子便不多费唇舌了。

Solution

字符数组比较法

public class Solution {
    public boolean isPalindrome(int x) {
        if (x >= Integer.MAX_VALUE || x < 0) return false;
        int digit = 0, x2 = x;
        while (x2 != 0) {
            x2 /= 10;
            digit++;
        }
        int[] A = new int[digit];
        while (x != 0) {
            A[--digit] = x % 10;
            x /= 10;
        }
        int left = 0, right = A.length-1;
        while (left < right) {
            if (A[left++] != A[right--]) return false;
        }
        return true;
    }
}

原数翻转比较法

public class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0) return false;
        long rvs = 0;
        int i = 0, org = x;
        while (x != 0) {
            i = x % 10;
            rvs = rvs * 10 + i;
            x /= 10;
        }
        return rvs == org;
    }
}