9. 回文数（Palindrome Number）

频次 ★★★ · 难度 🟢 · 高频：腾讯/美团

题目

判断一个整数是否是回文数（正读反读一样）。不能将整数转为字符串。

示例：

输入: 121
输出: true

输入: -121
输出: false  （反转后 121-，不等）

输入: 10
输出: false  （反转后 01 = 1，不等）

思路

反转一半数字：负数直接返回 false。将原数不断 % 10 取出末位，构造反转的后半部分 reverted，当原数 ≤ reverted 时说明已处理了一半位数。最后检查：偶数位时两者相等，奇数位时 reverted / 10 == x。

代码

public boolean isPalindrome(int x) {
    // 负数或末位为 0 但本身不是 0（如 10、120）不是回文
    if (x < 0 || (x % 10 == 0 && x != 0)) return false;
 
    int reverted = 0;
    while (x > reverted) {
        reverted = reverted * 10 + x % 10;
        x /= 10;
    }
 
    // 偶数位: x == reverted; 奇数位: x == reverted / 10
    return x == reverted || x == reverted / 10;
}

复杂度

• 时间：O(log₁₀ n) — 处理一半位数
• 空间：O(1)

边界条件

• 负数：-121 不是回文（负号不在数字部分）。
• 末位为 0 且非 0 的数：如 10、120 不是回文（反转后高位 0 被丢弃）。
• 个位数：0~9 都是回文，循环条件 x > reverted 不成立，直接返回 x == reverted（即 true）。
• Integer.MAX_VALUE：反转一半不会溢出，因为只处理一半位数。

变式

• 字符串版回文（125. 验证回文串）：双指针法，跳过非字母数字字符。
• 回文链表（234. 回文链表）：快慢指针找中点 + 反转后半段比较。
• 最长回文子串（5. 最长回文子串）：中心扩展法或 DP。

易错点

• 末尾为 0（如 10）：我们的逻辑不能简单地 x % 10 == 0 就返回 false，要注意 x = 0 本身是回文，需要 x != 0 条件。
• 奇数位数的处理：如 121，最后 reverted = 12、x = 1，需要检查 x == reverted / 10（去掉反转数的最后一位）。
• 不能用字符串是本题的约束：不能用 new StringBuilder(x + "").reverse() 来偷懒。

面试追问

• 为什么不反转整个数字？ 反转整个数字可能溢出，反转一半避免了溢出问题，且只需处理一半位数更高效。
• 如果允许转字符串怎么实现？ 双指针首尾比较即可，时间复杂度不变但空间 O(n)（字符串存储）。
• 如何判断一个长整数（如 64 位）是否为回文？ 同样思路，把 int 换成 long，溢出问题也不存在了，甚至可以反转全部。

关联题

• 同套路：125. 验证回文串（字符串版回文）
• 进阶：5. 最长回文子串（中心扩展法）
• 易混：7. 整数反转（反转全部而非一半，需处理溢出）
• 知识点：回文通用判定见双指针与滑动窗口