LeetCode 9：回文數判斷

題目：判斷整數是否回文（正讀反讀相同）。負數非回文。禁止使用額外空間（即不能轉字符串）。

解法一：數字翻轉半邊比較（推薦）

將數字後半部分翻轉，與前半部分比較。具體：

• x < 0 或 (x % 10 == 0 && x != 0) 直接 false。
• 循環 reverted = reverted * 10 + x % 10; x /= 10; 直到 x <= reverted。
• 最終 x == reverted（偶數位）或 x == reverted / 10（奇數位，中間位忽略）。

時間 O(log n)，空間 O(1)，無溢出風險（只翻轉一半）。

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

解法二：首尾位比較（需先求最高位權重）

求 div = 10^k 使 x / div < 10。循環比較 x / div 與 x % 10，然後 x = (x % div) / 10; div /= 100。邏輯直觀但略繁瑣。

錯誤嘗試：轉字符串

雖然 to_string 簡單，但違反「無額外空間」限制，且性能差（動態分配）。

總結

半翻轉法是標準答案：巧妙避開溢出、無額外空間、代碼極短。體現「原地算法」設計技巧。