Determine whether an integer is a palindrome. Do this without extra space.(source)
判断一个数字是否为回文数，并且不使用额外的存储空间。
“回文”是指正读反读都能读通的句子，那么回文数，就很容易理解，，就是指一个数正反读的值是相同的。还有一个要求是不要使用额外的存储空间。
Hints:
要将一个数的最高位与最低位比较，取出一个数的最低位容易（x%10），但要得到高位却很难。
Solution 1:
首先得知道一个负数的处理方法，比如-1是不是一个回文数，在这里我们认为负数都不是回文数。 直观的讲，判断一个回文数可以把该数reverse，如下：
int reverse(int num) { assert(num >= 0);// 只考虑非负数 int rev = 0; while (num != 0) {rev = rev*10 + num%10;num /= 10; } return rev;}
然后与原数比较，return reverse(num)==num; 该算法使用了一个额外的存储空间，并且没有考虑到越界的问题，例如在C++中INT_MAX=2^31-1 = 2147483647的回文数为7463847412就越界了，因此该方法不是很好的方法。
Solution 2:
另外可以将数字转换成字符串之后，判断一个字符串是否为回文。
string int2str(int x){string ret;if( x == 0 )ret.push_back(‘0’);while( x ){ret.push_back(‘0’ + x%10);x /= 10;}reverse(ret.begin(), ret.end()); // 字符串逆序return ret;}// 判断回文字符串bool isPalindrome(string str) {int low = 0;int high = str.length()-1;while(low < high){if(str[low] != str[high])return false;low++;high–;}return true;}
该方法需要与数字长度相同的字节数的存数空间，也不是一个零存储空间的算法。
Solution 3:
利用高位和低位相等的思想，不会越界，却需要额外的存储空间。
bool isPalindrome(int x) { if (x < 0) return false; int div = 1; while (x / div >= 10) {div *= 10;// div的最高位为1，长度与x相同 }while (x != 0) {(h != l) return false;x = (x % div) / 10;// 去掉x的最高位和最低位div /= 100; } return true;}Solution 4：
零存储方法。利用递归的思想，利用栈内存，达到了零存储的目的。
bool isPalindrome(int x, int &y) {; if (x == 0) return true; if (isPalindrome(x/10, y) && (x%10 == y%10)) {// 每次执行到 x%10 == y%10 的时候 x 为前i位，y表示前（n+1-i）位y /= 10;return true; } else {return false; }}bool isPalindrome(int x) { return isPalindrome(x, x);}
不做任何解释。没有人明白，
