LeetCode Palindrome Number：不轉字符串判斷回文數 O(1) 空間

題目回顧

判斷整數是否為回文數。不能使用額外空間（即不能轉字符串）。負數不是回文。

核心思路：首尾位比較 + 逐層剝離

1. 先找到最高位權值 div（如 12321 → div=10000）
2. 循環比較最高位 x/div 和最低位 x%10
3. 相等則剝離首尾：x = (x % div) / 10，div /= 100
4. 直到 x == 0

C++ 代碼

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0) return false;
        int div = 1;
        while (x / div >= 10) div *= 10; // 找最高位權值
        while (x > 0) {
            int left = x / div;
            int right = x % 10;
            if (left != right) return false;
            x = (x % div) / 10; // 去首尾
            div /= 100;         // 位數減 2
        }
        return true;
    }
};

另一種思路：反轉後半段

將數字後半段反轉，與前半段比較。需處理奇數位中間數字。

bool isPalindrome(int x) {
    if (x < 0 || (x % 10 == 0 && x != 0)) return false;
    int reverted = 0;
    while (x > reverted) {
        reverted = reverted * 10 + x % 10;
        x /= 10;
    }
    return x == reverted || x == reverted / 10;
}

複雜度

• 時間：O(log₁₀ n)
• 空間：O(1)

總結

首尾比較法直觀易懂，反轉後半段法更優雅且常數因子更小。面試建議掌握兩種，說明反轉後半段的邊界條件（x%10==0 排除 10, 100 等）。