題目網址：https://leetcode.cn/problems/add-two-numbers/

題意：給兩個非空 linked list 表示兩個非負整數, 每位數字都是按照逆序（e.g. 個位數在前, 十位數在後）儲存的, 且每一個 node 只能存一位數字。請將兩數相加, 並以相同型式返回和的 linked list。

除了數字 0 以外, 其他數字都不會以 0 作為開頭。

Solution：

想法：用 dummy 記住新的 linked list 開頭, tail 用來更新新的 linked list 之尾端。除此之外, 還要考慮進位(carry bit)和以下特殊情況：

  • 兩個整數長度不一（e.g. 123 + 4567）
    ➔ 當 node 為 NULL 時, 把 node->val 設為 0

  • 進位導致輸出比原本最長整數還長（e.g. 1 + 99 = 100）
    ➔ loop 終止條件須判斷 carry bit 是否為 0

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int carry = 0;
        ListNode *dummy = new ListNode(0), *tail = dummy;

        while (l1 || l2 || carry) {
            int sum = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + carry;
            tail->next = new ListNode(sum % 10);
            tail = tail->next;
            carry = sum / 10;

            // 更新 ptr, 若 ptr 為 null, 則不能用 ptr->next, 而是直接設成 null
            l1 = l1 ? l1->next : nullptr;
            l2 = l2 ? l2->next : nullptr;
        }
        return dummy->next;
    }
};
  • time：$O(max(m,n))$ ➔ while loop 終止是取決最長的 linked list 長度
  • space：$O(max(m,n))$ ➔ 新的 linked list 長度取決於最長的 linked list 長度