LeetCode 9：回文數判斷 —— 不用額外空間的數學解法

題目

判斷整數是否為回文數。不能使用額外空間（即不能轉字符串）。負數不是回文；個位為 0 的非零數也不是（如 10）。

核心思路：只反轉一半數字

將數字後半部分反轉，與前半部分比較。循環條件 reverted < original 保證只處理一半，避免溢出。

C++ 標準解法

class Solution {
public:
    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;
        }
        // 偶數位：x == reverted；奇數位：x == reverted/10
        return x == reverted || x == reverted / 10;
    }
};

Java 版（官方同款）

public boolean 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;
}

Python 版（雙指針法）

class Solution:
    def isPalindrome(self, x):
        if x < 0: return False
        div = 1
        while x // div >= 10: div *= 10
        while x:
            left, right = x // div, x % 10
            if left != right: return False
            x = (x % div) // 10
            div //= 100
        return True

Python 字符串法（作弊但簡潔）

def isPalindrome(self, x):
    return str(x) == str(x)[::-1]

關鍵點總結

1. 邊界處理：負數、個位 0 直接 false。
2. 只反轉一半：循環條件 x > reverted 自然停在中點，無需預知位數。
3. 奇偶兼容：返回時同時檢查 x == reverted（偶數位）與 x == reverted/10（奇數位）。
4. 溢出安全：因只反轉一半，reverted 永遠不超過 INT_MAX/10，無溢出風險。

複雜度

• 時間：O(log₁₀ n)，即數字位數。
• 空間：O(1)。