如何不转字符串判断一个整数是否回文？（LeetCode 9）

简化版

判断一个整数是否是回文数（正着读反着读一样，如 121、1331）。负数一律不是（-121 反读是 121-）。进阶要求「不转成字符串」时，用反转一半数字的技巧：不断取 x 的末位拼成「反转后半段」reverted，同时缩短 x，当 x <= reverted 时说明已处理到中间，比较 x == reverted（偶数位）或 x == reverted / 10（奇数位，去掉中间位）。只反转一半可避免整数溢出。

详细版

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;   // 后半段末位拼进 reverted
        x /= 10;                              // x 去掉末位
    }
    // 偶数位：x == reverted；奇数位：中间那位在 reverted 末尾，去掉再比
    return x == reverted || x == reverted / 10;
}

负数直接 false；末位 0 且非 0 的数（10、120）也 false（反转后前导 0）。
只反转一半：当 x <= reverted 时，说明已经处理过半，无需全部反转——避免溢出。
奇偶处理：偶数位比 x == reverted；奇数位 reverted 多含中间位，reverted / 10 去掉它。
复杂度：O(log₁₀ x)（只处理一半位数）。

完整版教学

一、最简单的思路：转字符串

最直接：把 x 转成字符串，用双指针从两端向中间比，或直接判断 str.equals(反转后的str)。简单可靠。但面试常追加要求「不转字符串、用纯数学方法」，以考察对数字操作和溢出的理解——这才是本题的考点。

二、进阶：为什么「反转一半」而不是全部

一个自然想法是「把整个 x 反转，再和原 x 比较」——但反转整个数可能溢出（如 2147483647 反转成 7463847412 超过 int 范围）。为避免溢出，技巧是只反转后一半，和前一半比较：

不断把 x 的末位取出，拼到 reverted（反转的后半段）；同时 x 除以 10 缩短。
当 x <= reverted 时停止——此时 x 是前半段、reverted 是反转的后半段，已经各占一半。
因为只反转一半，reverted 最多是原数一半的位数，绝不会溢出。

三、停止条件与奇偶处理

停止条件 x > reverted：循环让 reverted 从后往前吃、x 从前往后缩，当 x 不再大于 reverted，说明已经吃过中点。

停止后分两种情况：

偶数位数（如 1221）：x 缩成 12（前半），reverted 变成 12（后半 21 反转）。直接 x == reverted 即回文。
奇数位数（如 12321）：x 缩成 12，reverted 变成 123（中间的 3 被算进了后半段）。此时中间位 3 在 reverted 末尾，比较时去掉它：x == reverted / 10（123/10 = 12 == x）。中间位不影响回文性，去掉即可。

所以最终判断是 x == reverted || x == reverted / 10，同时覆盖奇偶。

四、两个边界特判

负数：x < 0 一律不是回文（负号只在前面，反读对不上）。
末位是 0 且 x ≠ 0：如 10、120，它们反转后会有前导 0（10 → 01），而整数没有前导 0 表示，所以这类不是回文。用 x % 10 == 0 && x != 0 特判返回 false。（0 本身是回文，要排除在外。）

这两个特判放在循环前，避免逻辑出错。

五、易错点

反转整个数导致溢出：所以要「只反转一半」。若用 long 反转全部再比也行，但「反转一半」是更优雅、纯 int 的解法。
忘记奇数位的 reverted / 10：只写 x == reverted 会漏掉所有奇数位回文。
忘记末位 0 特判：10 会被误判。
0 是回文：x = 0 应返回 true，特判条件里 x != 0 保证不误伤 0。

六、反转一半如何区分奇偶位数

循环条件 x>reversedHalf 让我们只搬运后半部分数字。偶数位数停止时两半相等；奇数位数停止时反转部分比剩余部分多包含中间位，因此比较 x==reversedHalf/10。中间位不影响左右镜像关系，应被除掉。

1221: x=1221, rev=0
取 1 -> x=122, rev=1
取 2 -> x=12, rev=12
停止，12==12 -> 回文
12321 最终 x=12, rev=123
去掉中间位 rev/10=12
12==12 -> 回文

校验维度	本题必须保持的结论
循环/递推不变量	每轮后，rev 是原数已取后缀的逆序，x 是尚未处理的前缀。
边界条件	负数不是回文；正数末位为 0 时除 0 本身外都不是回文。
复杂度与代价	只处理约一半十进制位，时间 O(log₁₀n)，空间 O(1)，且不会反转到 int 溢出。
自检方式	用最小输入、典型输入和触及边界的输入分别手推，结果应与定义一致。

这组推演的作用不是替代证明，而是把抽象规则落到每一步状态变化上。面试写完代码后，应主动指出不变量如何保证不漏解，以及边界为何不会越界或死循环。若手推结果与定义不一致，应先修正状态语义，而不是继续给代码打补丁。

七、面试现场如何验证这道题

数学题不能只凭样例相信公式，必须同时核对定义域、推导条件和定宽整数边界。本题应先复述这条不变量：每轮后，rev 是原数已取后缀的逆序，x 是尚未处理的前缀。只有代码的初始化、更新顺序和终止条件都维持它，样例通过才具有证明力。

典型路径从“1221: x=1221, rev=0”开始手推，最后应得到“12==12 -> 回文”。
边界复核：负数不是回文；正数末位为 0 时除 0 本身外都不是回文。
代价复核：只处理约一半十进制位，时间 O(log₁₀n)，空间 O(1)，且不会反转到 int 溢出。
用 0、1、最小合法值和最大合法值检查公式的定义域。
乘法、取绝对值或取负前先判断是否可能触及 Integer.MIN_VALUE 等不对称边界。
若算法依赖单调性、抵消或整除关系，要明确题设保证何时成立、何时必须额外验证。

最后要主动构造一个“少写一次循环、改变一个不等号或交换两行更新就会失败”的反例。能说清反例破坏了哪条不变量，比只报出复杂度更能证明真正掌握了算法。

记忆钩子：本题的代码可以压缩，但“每轮后，rev 是原数已取后缀的逆序，x 是尚未处理的前缀。”这条正确性主线不能省。

八、常见误区与追问

误区：所有负数去掉负号后都可以判回文。 题目把负号视为表示的一部分，负数直接不是回文。
误区：10 是回文，因为反转后前导零可忽略。 反转字符串应为 01，与 10 不同；末位 0 的正数应提前排除。
误区：停止后只比较 x==rev。 奇数位数需要忽略 rev 的中间位，比较 x==rev/10。
追问：为何半反转不会溢出？ 只构造原数约一半位数，规模远小于完整反转的最坏值。
追问：0 是否是回文数？ 是，单个数字正反相同，且末位 0 特判应排除 x==0。
追问：转字符串法有什么代价？ 实现简单但需要 O(log n) 字符空间，不满足进阶的 O(1) 空间目标。

九、加强记忆

判断回文数（不转字符串）= 反转后一半和前一半比。先特判：负数、末位 0 且非 0（前导零）→ false。循环 while (x > reverted)：reverted = reverted*10 + x%10、x /= 10——反转后半段、缩短前半段，只反转一半避免溢出。停止后 x == reverted（偶数位）或 x == reverted/10（奇数位去掉中间位） 即回文。O(log x)。核心：反转一半、比前后半、奇数位除掉中间那位。

简化版

详细版