LeetCode 9. Palindrome Number：無額外空間判斷回文數

問題描述

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

數學反轉法

逐位提取數字構建反轉數，比較與原數是否相等：

public boolean isPalindrome(int x) {
    if (x < 0) return false;
    if (x == 0) return true;
    
    int original = x;
    int reversed = 0;
    while (x != 0) {
        reversed = reversed * 10 + x % 10;
        x /= 10;
    }
    return original == reversed;
}

溢出風險與優化

reversed 可能溢出 int 範圍（如 1999999999 反轉超過 INT_MAX）。改進：

• 使用 long 存儲 reversed
• 或僅反轉一半數字：while (x > reversed) reversed = reversed*10 + x%10, x/=10; 最後比較 x==reversed || x==reversed/10

半反轉法代碼

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

關鍵點總結

1. 負數直接返回 false
2. 尾部為 0 的非零數（如 10, 100）不可能是回文
3. 半反轉避免溢出，時間 O(log n)，空間 O(1)
4. 奇數長度時中間位在 reverted/10 中被忽略