题目链接：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.

这道题的要求是判断整数是否是回文。（不使用额外空间）

思路是同判断字符串是否是回文类似，采用2个指针l和r，分别从左侧和右侧向中间移动，同是判断l和r指向的数位上的数字是否相同。

那么问题来了，怎么构造l和r？

l指向数字的最高位，因此，可以先遍历一遍数组，获取其位数，这样就可以获取其最高位了。而r就等于该数字模10的结果。

而数字是负数是，均不是回文。

时间复杂度：O(n)（由数字位数决定）

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution
{
public:
    bool isPalindrome(int x)
    {
        if(x < 0)
            return false;
        
        int h = 1;
        while(x / h >= 10)
            h *= 10;
        
        while(x != 0)
        {
            int l = x / h, r = x % 10;
            if(l != r)
                return false;
            x = x % h / 10;
            h /= 100;
        }
        
        return true;
    }
};