題目大意

給定兩個非空鏈表表示兩個非負整數，數位按逆序存儲（個位在頭節點）。將兩數相加，結果同樣以逆序鏈表返回。

輸入: (2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出: 7 -> 0 -> 8
解釋: 342 + 465 = 807

解題思路

模擬豎式加法：同步遍歷兩鏈表，對應節點相加並處理進位。難點在於鏈表長度不一、最終進位產生新節點、內存管理。

AC 代碼（優化版）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* tail = &dummy;
        int carry = 0;
        
        while (l1 || l2 || carry) {
            int sum = carry;
            if (l1) { sum += l1->val; l1 = l1->next; }
            if (l2) { sum += l2->val; l2 = l2->next; }
            
            carry = sum / 10;
            tail->next = new ListNode(sum % 10);
            tail = tail->next;
        }
        return dummy.next;
    }
};

關鍵點解析

1. 虛擬頭節點：簡化頭節點特殊處理，統一插入邏輯。
2. 循環條件：l1 || l2 || carry 覆蓋三種情況——兩鏈表未盡、其中一鏈表已盡、最高位產生進位。
3. 原地複用：若允許修改輸入鏈表，可直接在較長鏈表上修改，節省空間（LeetCode 通常不要求）。
4. 內存洩漏：競技編程中忽略釋放；工程代碼需提供銷毀函數或使用智能指針。

本地測試主函數

int main() {
    // 建立 2->4->3
    ListNode *l1 = new ListNode(2);
    l1->next = new ListNode(4);
    l1->next->next = new ListNode(3);
    
    // 建立 5->6->4
    ListNode *l2 = new ListNode(5);
    l2->next = new ListNode(6);
    l2->next->next = new ListNode(4);
    
    Solution s;
    ListNode* res = s.addTwoNumbers(l1, l2);
    while (res) {
        cout << res->val;
        if (res->next) cout << "->";
        res = res->next;
    }
    cout << endl;
    return 0;
}

進階變體

• 正序存儲：先反轉鏈表或用棧暫存，再按相同邏輯處理。
• 超大整數：節點值可存 1e9 基數，減少節點數。
• 多數相加：維護指針數組，每輪累加所有非空節點。

心得

鏈表題核心在指針操作熟練度。虛擬頭節點、尾指針維護、循環不變量設計是通用技巧。本題看似簡單，實則考察邊界處理完備性——這正是工程代碼質量的分水嶺。