LeetCode 9. 回文数

◎

本节目标

用数字的一半反转判断回文，避免完整反转可能造成的溢出。

这道题承接模拟、递推与边界：把整数按位拆开，但只处理必要的一半数字。

查看原题

题意与约束

判断整数 x 从左向右读与从右向左读是否相同。题目约束为 -2^31 <= x <= 2^31 - 1，返回布尔值。

• 负数带有负号，例如 -121 倒读不是原数。
• 除 0 外，末位为 0 的数不可能是回文；例如 10 不会写成 01。
• 0 本身是回文数。

为什么只反转一半

完整反转整数后再比较虽然直观，却可能在反转过程中超出整数范围。回文的两半必然镜像，因此只需从末位取数，反转到已经处理的后半部分不少于剩余前半部分为止。

这样最多处理一半位数，也不需要把整数转换成字符串。

循环不变量

循环开始时，x 保存尚未处理的前半段，reversed 保存原数末尾若干位按相反顺序组成的数。每轮把 x 的个位追加到 reversed，再删去 x 的个位。

当 x <= reversed 时，两部分已经在中间相遇或交叉，可以开始比较。

奇数位与偶数位如何收口

偶数位回文会在中间两侧相遇，例如 1221 最终得到 x = 12、reversed = 12，直接比较即可。

奇数位回文的中位数会被放进 reversed 的个位，例如 121 得到 x = 1、reversed = 12。去掉中位数后比较 x 与 reversed / 10；整数除法会丢弃这个个位。

代码实现

两份源码都先排除负数与非零末尾为零的情况，再按位反转一半。

C++

C++17

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }

        int reversed = 0;
        while (x > reversed) {
            reversed = reversed * 10 + x % 10;
            x /= 10;
        }
        return x == reversed || x == reversed / 10;
    }
};

Python

Python 3

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0 or (x % 10 == 0 and x != 0):
            return False

        reversed_number = 0
        while x > reversed_number:
            reversed_number = reversed_number * 10 + x % 10
            x //= 10
        return x == reversed_number or x == reversed_number // 10

复杂度分析

• 时间复杂度：O(log x)，循环只处理约一半十进制位数。
• 空间复杂度：O(1)，只使用两个整数变量。

易错点

• 把负数当成回文，忽略了负号。
• 将 10 当成回文；只有 0 可以以零结尾且保持回文。
• 奇数位比较时忘记除以 10 去掉中位数。
• 先完整反转再比较，既多做一半工作，也可能引入溢出风险。

模式迁移

“从两端向中间收口”不仅能用在回文判断。字符串双指针、链表找中点、数字拆位比较都可以先问：是否真的需要保存或处理完整对象？若两侧只需在中点会合，半程状态往往更安全也更省空间。