9. Palindrome Number（回文）

问题描述：
Determine whether an integer is a palindrome. Do this without extra space.

Some hints:
Could negative integers be palindromes? (ie, -1)
不可以
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.

思路：

如提示所说，可以将x转换成字符串，然后遍历判断，也可以翻转整数，分别需要注意额外空间和整数溢出的问题。
那用数组存放应该也算是额外空间了吧。
那就得分别取首末数字进行比较，然后剔除首末数字之后再比较，直到x=0
按照这个思路写了，测试了几个数，发现可以，代码如下：

  public boolean isPalindrome(int x) {
        if(x<0) return false;
        if(x<10) return true;
        int base = 1;
        while(x/base >= 10){
            base *= 10; //为了找到可以取得最高位数字的基数
        }
        while(x>9){
            int leftDigit = x/base;
            int rightDigit = x%10;
            if(leftDigit != rightDigit) return false;
            x -= leftDigit*base; //去掉最高位
            base /= 10;
            x /= 10; //去掉最低位
        }
        return true;
    }

但最后提交的时候出现了一个错误的示例：1000021，然后发现此种方案碰到这种情况是不能解决的，因为进行了去掉最高位的操作后，整数一下子成了两位数，0无法进行比较了。之后去找了其他人的解决方法，发现了下面的这种解法：

  public boolean isPalindrome(int x) {
        if(x<0 || (x!=0 && x%10==0)) return false;
        int res = 0;
        while(x>res){
            res = res*10 +x%10;
            x /= 10;
        }
        return (x==res || x==res/10);//位数为偶数和奇数
    }

和reverse integer思路差不太多，但只把数字的一半进行了翻转，不会产生溢出。