LeetCode 9 Palindrome Number：無額外空間判斷回文數的多種方法

問題描述

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

方法一：完全反轉 (溢出風險)

bool isPalindrome(int x) {
    if (x < 0) return false;
    long long rev = 0, orig = x;
    while (x) { rev = rev * 10 + x % 10; x /= 10; }
    return rev == orig;
}

用 `long long` 避免溢出，但違反「無額外空間」精神。

方法二：半反轉 (推薦，O(1) 空間)

只反轉後一半數字，與前一半比較。

bool isPalindrome(int x) {
    if (x < 0 || (x % 10 == 0 && x != 0)) return false;
    int rev = 0;
    while (x > rev) {
        rev = rev * 10 + x % 10;
        x /= 10;
    }
    return x == rev || x == rev / 10;  // 奇數長度去掉中間位
}

循環條件 `x > rev` 確保只反轉一半。奇數長度時 `rev` 多一位，比較時 `/10` 去掉。

方法三：首尾位對比 (直觀)

bool isPalindrome(int x) {
    if (x < 0) return false;
    int div = 1;
    while (x / div >= 10) div *= 10;  // 最高位權重
    while (x) {
        int left = x / div;
        int right = x % 10;
        if (left != right) return false;
        x = (x % div) / 10;  // 去掉首尾位
        div /= 100;
    }
    return true;
}

Python 版本 (教學參考)

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

方法對比

關鍵邊界測試

• 0 → true
• -121 → false
• 10 → false (尾部 0 導致反轉首位為 0)
• 1001 → true
• 2147447412 → true (接近 INT_MAX 的回文)
• 2147483647 → false (INT_MAX)