LeetCode 2. 兩數相加：鏈表模擬加法 C 語言解法詳解

LeetCode 2. 兩數相加：鏈表模擬加法 C 語言解法詳解

本題要求將兩個非負整數以逆序鏈表形式存儲（每個節點一位數字），模擬豎式加法計算並返回結果鏈表。文章詳細拆解進位邏輯、邊界處理及內存管理，提供優化版 C 語言實現。

題目理解

• 輸入：兩個單鏈表 `l1`、`l2`，節點值為 0-9，代表逆序數字（如 2→4→3 代表 342）。
• 輸出：表示和的逆序鏈表（如 342+465=807 → 7→0→8）。
• 核心難點：處理鏈表長度不同、最後進位產生新節點、釋放輸入鏈表節點（若題目允許修改原鏈表）。

算法思路：模擬豎式加法

1. 初始化結果鏈表頭指針 `phead`、當前節點指針 `curp`、進位標誌 `flag=0`。
2. 同時遍歷 `l1`、`l2`，直到兩者均為空。
3. 每輪取當前節點值（若鏈表已盡則為 0），加上進位 `flag`。
4. 新節點值 = 總和 % 10，更新 `flag` = 總和 / 10。
5. 將新節點接入結果鏈表，移動 `curp`。
6. 遍歷結束後，若 `flag==1` 需額外創建節點存儲進位 1。

優化版 C 語言實現

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode *phead = NULL;   // 結果鏈表頭
    struct ListNode *curp = NULL;    // 結果鏈表尾
    struct ListNode *cur1 = l1, *cur2 = l2;
    int carry = 0;                   // 進位

    while (cur1 || cur2) {
        int v1 = cur1 ? cur1->val : 0;
        int v2 = cur2 ? cur2->val : 0;
        int sum = v1 + v2 + carry;

        struct ListNode *node = (struct ListNode*)malloc(sizeof(struct ListNode));
        node->val = sum % 10;
        node->next = NULL;
        carry = sum / 10;

        if (!phead) {
            phead = curp = node;
        } else {
            curp->next = node;
            curp = node;
        }

        if (cur1) cur1 = cur1->next;
        if (cur2) cur2 = cur2->next;
    }

    if (carry) { // 處理最高位進位
        struct ListNode *node = (struct ListNode*)malloc(sizeof(struct ListNode));
        node->val = 1;
        node->next = NULL;
        curp->next = node;
    }
    return phead;
}

關鍵點解析

• 統一取值邏輯：使用三元運算符 `cur1 ? cur1->val : 0` 避免分支臃腫。
• 尾插法構建結果鏈表：維護 `curp` 指向尾節點，O(1) 插入新節點。
• 進位處理：循環結束後單獨檢查 `carry`，避免漏掉最高位進位（如 5+5=10）。
• 內存管理：本實現未釋放輸入鏈表節點，若題目要求釋放，可在取值後 `free` 原節點（注意先保存 `next` 指針）。

複雜度分析

• 時間複雜度：O(max(m, n))，m、n 為兩鏈表長度。
• 空間複雜度：O(max(m, n))，結果鏈表長度最多比較長鏈表多 1 位。

總結

本題考察鏈表基本操作與初等數學模擬。關鍵在於簡潔處理不同長度鏈表、正確維護進位、規範構建新鏈表。優化版代碼邏輯清晰、分支極少，是面試與刷題的推薦寫法。