3.3　回文数

题目描述（第9题）

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

示例1

输入：121

输出：True

示例2

输入：-121

输出：False

解释：从左向右读为-121，从右向左读为121-，因此它不是一个回文数。

示例3

输入：10

输出：False

解释：从右向左读为01，因此它不是一个回文数。

进阶

你能不将整数转化为字符串来解决这个问题吗？

如果将整数转化为字符串，问题就转化为前面讲过的判断字符串的回文算法。我们可以不将整数转化为字符串来解决这个问题吗？当然可以，并且也十分简单。

思路

在计算机程序中，整数中的各位数字不能像数组那样被随机访问，因此采用头/尾指针的方法行不通。

如果我们能够得到原数的倒序，那么只需要和原数进行比较，观察是否相同就可以了。一个简单的做法是将其转化为字符串然后让字符串逆序，但是这种做法还不如转化为字符串之后直接使用双指针，并且题目进阶中要求不将整数转化为字符串来解决这个问题，问题的关键在于得到原数的倒序。一个思路是从高位到低位依次得到整数每一位上的值，然后从低位到高位构建新的值。

不妨假设要判断的整数为x，我们可以通过x%10（取余操作）获取x的最后一位，然后将x整除10得到的商更新到x。这样不断循环直到x等于0为止。最后只要判断从后往前取的数和原来的数是否相同即可。

简单来说，检验一个整数是否为回文数，对于正数只需要检查它是否等于它的倒序即可，而构造一个整数的倒序，可以按位处理（这里假设倒序的整数不会越界）。

代码

复杂度分析

●　时间复杂度：O(n)，其中n为整数的位数。

●　空间复杂度：O(1)。