LeetCode Palindrome Number 回文數判斷 (不使用額外空間)

問題

判斷整數是否為回文數。不允許轉字符串 (額外空間)。負數非回文。反轉整數可能溢出。

解法：反轉後半部分比較

將數字後半部分反轉，與前半部分比較。偶數位：反轉後相等；奇數位：反轉後去掉中間位 (除 10) 比較。避免完全反轉溢出。

代碼 (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;
        }
        return x == reverted || x == reverted / 10;
    }
};

原理

• 尾數為 0 的非零數不可能是回文 (首位不能為 0)。
• 循環條件 `x > reverted` 確保只反轉一半。
• 奇數位時 `reverted` 多一位中間數，除 10 後比較。

複雜度

O(log₁₀ n) 時間，O(1) 空間。