跳到主要内容

回文数

问题​

给你一个整数 x，如果 x 是一个回文整数，返回 true；否则，返回 false。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。

来源：LeetCode 9. 回文数

示例：

输入：x = 121
输出：true

输入：x = -121
输出：false（从右向左读为 121-）

输入：x = 10
输出：false（从右向左读为 01）

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

答案​

解法一：转字符串​

最直观的方式是将数字转为字符串，然后判断字符串是否回文：

palindrome-number-string.ts
function isPalindrome(x: number): boolean {
  const str = String(x);
  return str === str.split("").reverse().join("");
}
注意

这种方式虽然简单，但需要额外的字符串空间，且面试中通常要求不转字符串的解法。

解法二：双指针（字符串）​

将数字转为字符串后，使用双指针从两端向中间比较：

palindrome-number-two-pointer.ts
function isPalindrome(x: number): boolean {
  const str = String(x);
  let left = 0;
  let right = str.length - 1;

  while (left < right) {
    if (str[left] !== str[right]) return false;
    left++;
    right--;
  }

  return true;
}
  • 时间复杂度：O(n)O(n)，nn 为数字位数
  • 空间复杂度：O(n)O(n)，存储字符串

解法三：反转一半数字（最优解）​

核心思路

不转字符串，只反转数字的后半部分，然后与前半部分比较。当反转的后半部分 ≥ 前半部分时，说明已经处理到中间位置。

palindrome-number-half-reverse.ts
function isPalindrome(x: number): boolean {
  // 负数不是回文数；末尾为 0 的正数也不是（除了 0 本身）
  if (x < 0 || (x % 10 === 0 && x !== 0)) return false;

  let reversed = 0;
  while (x > reversed) {
    reversed = reversed * 10 + (x % 10);
    x = Math.floor(x / 10);
  }

  // 偶数位：x === reversed
  // 奇数位：x === Math.floor(reversed / 10)（中间那位在 reversed 里）
  return x === reversed || x === Math.floor(reversed / 10);
}

执行过程示例（x = 12321）：

步骤xreversed说明
初始123210
第 1 步12321取末位 1
第 2 步12312取末位 2
第 3 步12123x < reversed，退出循环
结果12 === Math.floor(123/10) = 12奇数位，去掉中间数后相等

复杂度分析：

  • 时间复杂度：O(log⁡10n)O(\log_{10} n)，只处理一半的数字位数
  • 空间复杂度：O(1)O(1)，只使用常数空间

解法四：完全反转数字​

将整个数字反转后与原数比较：

palindrome-number-full-reverse.ts
function isPalindrome(x: number): boolean {
  if (x < 0) return false;

  const original = x;
  let reversed = 0;

  while (x > 0) {
    reversed = reversed * 10 + (x % 10);
    x = Math.floor(x / 10);
  }

  return original === reversed;
}
补充

完全反转虽然代码更简洁，但理论上存在整数溢出风险（虽然在 JavaScript 中由于使用浮点数不会溢出，但在 C++/Java 中需要注意）。反转一半数字的方式天然避免了溢出问题。

各解法对比​

解法时间复杂度空间复杂度是否转字符串溢出风险
转字符串 reverseO(n)O(n)O(n)O(n)是无
双指针（字符串）O(n)O(n)O(n)O(n)是无
反转一半数字O(log⁡n)O(\log n)O(1)O(1)否无
完全反转数字O(log⁡n)O(\log n)O(1)O(1)否有（非 JS）

常见面试问题​

Q1: 为什么负数不是回文数？​

答案：

负数有负号 -，反过来读变成 121-，首尾不对称，所以所有负数都不是回文数。这是一个重要的边界条件，面试时应首先处理。

Q2: 为什么末尾为 0 的数（除了 0 本身）不是回文数？​

答案：

如果末尾是 0（如 10、120），反转后前导是 0（01、021），但整数不允许前导零，所以不可能等于原数。唯一的例外是 0 本身。

// 这个判断可以提前过滤，避免不必要的计算
if (x % 10 === 0 && x !== 0) return false;

Q3: 反转一半数字时，怎么知道已经到了一半？​

答案：

循环条件是 x > reversed。每次循环从 x 取走一位给 reversed，当 reversed 的位数追上或超过 x 时，说明已经到了中间位置：

  • 偶数位：x === reversed 时恰好各占一半
  • 奇数位：reversed 会多一位（包含中间数），需要 Math.floor(reversed / 10) 去掉中间数后比较

Q4: 回文数和回文字符串的判断有什么区别？​

答案：

维度回文数回文字符串
负数/特殊字符负数直接排除可能需要忽略特殊字符
前导零整数无前导零字符串可以有 "010"
最优方式数学运算反转一半双指针
空间要求可以 O(1)O(1)双指针也是 O(1)O(1)

对应的回文字符串判断（LeetCode 125）：

function isPalindromeString(s: string): boolean {
  const cleaned = s.toLowerCase().replace(/[^a-z0-9]/g, "");
  let left = 0;
  let right = cleaned.length - 1;

  while (left < right) {
    if (cleaned[left] !== cleaned[right]) return false;
    left++;
    right--;
  }

  return true;
}

Q5: 如何判断一个链表是否为回文？​

答案：

链表不能通过下标访问，常用快慢指针 + 反转后半部分：

interface ListNode {
  val: number;
  next: ListNode | null;
}

function isPalindromeList(head: ListNode | null): boolean {
  if (!head || !head.next) return true;

  // 1. 快慢指针找中点
  let slow: ListNode | null = head;
  let fast: ListNode | null = head;
  while (fast?.next?.next) {
    slow = slow!.next;
    fast = fast.next.next;
  }

  // 2. 反转后半部分
  let prev: ListNode | null = null;
  let curr = slow!.next;
  while (curr) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }

  // 3. 比较前半和反转后的后半
  let p1: ListNode | null = head;
  let p2: ListNode | null = prev;
  while (p2) {
    if (p1!.val !== p2.val) return false;
    p1 = p1!.next;
    p2 = p2.next;
  }

  return true;
}
  • 时间复杂度：O(n)O(n)
  • 空间复杂度：O(1)O(1)

Q6: 找到离 x 最近的回文数怎么做？​

答案：

这是 LeetCode 564，思路是将数字的前半部分镜像翻转来构造候选回文数：

function nearestPalindromic(n: string): string {
  const len = n.length;
  const half = n.slice(0, Math.ceil(len / 2));
  const halfNum = BigInt(half);

  // 构造 5 个候选值
  const candidates: bigint[] = [
    makePalindrome(halfNum, len),         // 镜像翻转
    makePalindrome(halfNum - 1n, len),    // 前半部分 -1
    makePalindrome(halfNum + 1n, len),    // 前半部分 +1
    10n ** BigInt(len - 1) - 1n,          // 99...9（少一位）
    10n ** BigInt(len) + 1n,              // 10...01（多一位）
  ];

  const num = BigInt(n);
  let result = -1n;
  let minDiff = BigInt(Number.MAX_SAFE_INTEGER);

  for (const c of candidates) {
    const diff = c > num ? c - num : num - c;
    if (diff === 0n) continue; // 排除自身
    if (diff < minDiff || (diff === minDiff && c < result)) {
      minDiff = diff;
      result = c;
    }
  }

  return result.toString();
}

function makePalindrome(half: bigint, totalLen: number): bigint {
  const s = half.toString();
  const mirror = totalLen % 2 === 0
    ? s + s.split("").reverse().join("")
    : s + s.slice(0, -1).split("").reverse().join("");
  return BigInt(mirror);
}

相关链接​