LeetCode 9. 回文数：两种高效解法详解

LeetCode入门级经典题——9.回文数，这道题看似简单，却藏着两种思路截然不同的高效解法，尤其适合刚接触算法的小伙伴巩固基础。话不多说，我们直接进入正题！

一、题目回顾

题目很简洁：给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

核心定义：回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

举几个例子帮大家快速理解：

• 输入：121 → 输出：true（正序121，倒序121，一致）

• 输入：-121 → 输出：false（正序-121，倒序121-，不一致）

• 输入：10 → 输出：false（正序10，倒序01，即1，不一致）

这里有个小细节：负数一定不是回文数（因为负号倒序后会在末尾，无法匹配）；末尾为0的非0整数也不是回文数（比如10、100，倒序后开头为0，和原数不一致），这两个细节会成为我们优化解法的关键。

二、解法一：完整反转整数（直观易懂）

1. 解法思路

最直观的思路就是：将整数完整反转，然后和原数对比，如果相等，就是回文数；否则不是。

核心步骤：

1. 先判断边界：如果 x < 0，直接返回 false（负数无回文）；

2. 定义两个变量：cur 保存原数的副本（用于后续反转操作，避免修改原数），revN 保存反转后的整数（初始为0）；

3. 循环反转：通过取余（cur % 10）获取 cur 的末尾数字，通过乘10（revN * 10）将反转后的数字左移一位，再加上末尾数字，同时将 cur 除以10（向下取整），直到 cur 变为0；

4. 对比反转后的数字（revN）和原数（x），相等则返回 true，否则返回 false。

2. 代码实现（TypeScript）

functionisPalindrome_1(x:number):boolean{if(x<0)returnfalse;letcur=x;letrevN=0;while(cur!==0){revN=cur%10+revN*10;cur=Math.floor(cur/10);}returnrevN===x;};

3. 解法分析

优势：思路简单、代码简洁，容易理解和上手，适合算法新手入门练习。

注意点：虽然题目中没有明确说明整数溢出的问题，但在实际场景中，反转后的整数可能会超过 Number 的最大范围（比如 x = 2^31 - 1，反转后会溢出）。不过在 LeetCode 这道题的测试用例中，这种情况不会出现，所以该解法可以直接通过。

时间复杂度：O(n)，n 是整数 x 的位数，因为循环次数等于 x 的位数。

空间复杂度：O(1)，只使用了3个变量（cur、revN、x），没有使用额外的空间。

三、解法二：反转一半整数（优化高效）

1. 解法思路

解法一的优化版：我们不需要反转整个整数，只需要反转整数的后半部分，然后和前半部分对比即可，这样可以减少一半的循环次数，效率更高。

核心逻辑：

1. 先判断边界：① x < 0 → false；② x 末尾为0且 x ≠ 0 → false（比如10、100）；

2. 定义变量 revertedNumber 保存反转的后半部分（初始为0）；

3. 循环反转后半部分：当 x > revertedNumber 时，说明还没反转到一半，继续取 x 的末尾数字，添加到 revertedNumber 中，同时 x 除以10（向下取整）；

4. 对比判断：循环结束后，有两种情况：

   • 如果 x 的位数是偶数（比如1221），则 x 应该等于 revertedNumber（x=12，revertedNumber=12）；

   • 如果 x 的位数是奇数（比如12321），则 x 应该等于 revertedNumber 除以10（去掉中间的数字3，x=12，revertedNumber=123 → 123/10=12）。

2. 代码实现（TypeScript）

functionisPalindrome_2(x:number):boolean{if(x<0||(x%10===0&&x!==0)){returnfalse;}letrevertedNumber:number=0;while(x>revertedNumber){revertedNumber=revertedNumber*10+x%10;x=Math.floor(x/10);}returnx===revertedNumber||x===Math.floor(revertedNumber/10);};

3. 解法分析

优势：相比解法一，循环次数减少了一半，效率更高；同时避免了反转整个整数可能出现的溢出问题（因为只反转一半，反转后的数字一定不会超过原数，也就不会溢出）。

注意点：边界判断的第二个条件（x % 10 === 0 && x !== 0）容易遗漏，比如输入10，不判断的话，循环后 x=1，revertedNumber=0，会误判为 true，加上这个条件就能避免。

时间复杂度：O(n/2) = O(n)，虽然循环次数减少一半，但时间复杂度的量级不变，不过实际运行速度会更快。

空间复杂度：O(1)，和解法一一样，只使用了少量变量，无额外空间消耗。

四、两种解法对比总结

五、刷题小技巧

1. 边界条件优先考虑：这道题的边界（负数、末尾为0的非0数）是解题的关键，先处理边界，能减少后续逻辑的复杂度，也能避免误判。

2. 优化思路的核心：当需要反转整数时，优先考虑“反转一半”，既能提高效率，又能规避溢出风险，这种“减半操作”在很多整数相关的算法题中都能用到。

3. 测试用例覆盖：写完代码后，记得测试几个典型用例（负数、末尾为0的数、奇数位整数、偶数位整数、单个数字），确保代码的正确性。

六、总结

LeetCode 9.回文数是一道非常适合入门的算法题，两种解法各有优劣，解法一适合新手理解思路，解法二适合优化效率。通过这道题，我们可以巩固“整数反转”的核心逻辑，同时学会关注边界条件和算法优化。