LeetCode Add Two Numbers：鏈表相加的兩種解法

LeetCode 2. Add Two Numbers 題目與解法

給定兩個非負整數鏈表，每個節點存一位，逆序存儲（個位在頭）。返回和鏈表。例：(2→4→3)+(5→6→4)=7→0→8（342+465=807）。

解法一：轉數字相加（易溢出，教學用）

遍歷鏈表構建 double 數值，相加後再構建鏈表。注意用 double 避免長整數溢出，判斷循環條件用 num >= 1。時間 O(max(m,n))，但浮點精度有風險，不推薦生產環境。

解法二：模擬豎式加法（標準解）

同步遍歷兩鏈表，維護進位 carry。新建哨兵節點 dummy，尾指針 tail。
while (l1 || l2) {
  sum = (l1?l1->val:0) + (l2?l2->val:0) + carry;
  tail->next = new ListNode(sum % 10);
  carry = sum / 10;
  tail = tail->next;
  if (l1) l1 = l1->next;
  if (l2) l2 = l2->next;
}
if (carry) tail->next = new ListNode(1);
return dummy->next;

代碼實現

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

關鍵點

• 哨兵節點簡化頭節點特判。
• 統一處理長度不同：缺位視為 0。
• 最終進位檢查：最高位可能產生新節點（如 999+1=1000）。
• 時間 O(max(m,n))，空間 O(max(m,n))（輸出鏈表）。

進階：正序存儲（LeetCode 445）

若鏈表正序存儲（最高位在頭），可先反轉鏈表再用上述邏輯，或用棧存儲節點再彈出相加，或遞歸對齊長度。核心思想相同。