2. 兩數相加

思路

用carry紀錄每次的進位，最初相加的來源是當前兩個鏈表的頭節點，後續將carry也列入考慮範圍
加完之後不斷往下指，並紀錄進位。
並用哨兵節點dummy方便回傳最初的起點。

又回到最初的起點~♫

只有在鏈表都到尾端，並且carry為 $0$ 時，相加才結束。

程式碼

鏈表

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

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(1)$