C語言判斷回文數算法：數字反轉法與字符串法對比實現

問題定義

回文數：正讀反讀相同的正整數，如 121、12321、4554。

算法一：數字反轉法（不轉字符串，O(1) 空間）

bool isPalindrome(int x) {
    if (x < 0) return false; // 負數不是回文
    if (x != 0 && x % 10 == 0) return false; // 尾數為0（如10、100）不可能回文
    
    int reversed = 0;
    while (x > reversed) { // 只反轉一半
        reversed = reversed * 10 + x % 10;
        x /= 10;
    }
    // 奇數位：reversed/10 == x；偶數位：reversed == x
    return x == reversed || x == reversed / 10;
}

優勢：無溢出風險（只反轉一半）、無額外空間、速度快。

算法二：字符串法（直觀易懂，O(log n) 空間）

bool isPalindromeStr(int x) {
    if (x < 0) return false;
    char buf[20];
    sprintf(buf, "%d", x);
    int len = strlen(buf);
    for (int i = 0, j = len - 1; i < j; i++, j--) {
        if (buf[i] != buf[j]) return false;
    }
    return true;
}

完整可運行程序

#include 
#include 
#include 

bool isPalindromeNum(int x) { /* 算法一實現 */ }
bool isPalindromeStr(int x) { /* 算法二實現 */ }

int main() {
    int test[] = {121, -121, 10, 12321, 123321, 0, 1001};
    for (int n : test) {
        printf("%d: 數字法=%s, 字符串法=%s\n", 
            n, isPalindromeNum(n)?"是":"否", isPalindromeStr(n)?"是":"否");
    }
    return 0;
}

輸出

121: 數字法=是, 字符串法=是
-121: 數字法=否, 字符串法=否
10: 數字法=否, 字符串法=否
12321: 數字法=是, 字符串法=是
123321: 數字法=是, 字符串法=是
0: 數字法=是, 字符串法=是
1001: 數字法=是, 字符串法=是

面試/考試加分點

• 處理 `INT_MAX` 反轉溢出：使用 `long` 或只反轉一半
• 說明時間複雜度 O(log n)、空間 O(1) vs O(log n)
• 擴展：判斷鏈表回文（快慢指針 + 反轉後半部分鏈表）