2. Add Two Numbers

  • Hardness: \(\color{orange}\textsf{Medium}\)
  • Ralated Topics: Linked List、Math、Recursion

一、題目

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example 1:
addtwonumber1

  • Input: l1 = [2,4,3], l2 = [5,6,4]
  • Output: [7,0,8]
  • Explanation: 342 + 465 = 807

Example 2:

  • Input: l1 = [0], l2 = [0]
  • Output: [0]

Example 3:

  • Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
  • Output: [8,9,9,9,0,0,0,1]

Constraints:

  • The number of nodes in each linked list is in the range [1, 100].
  • 0 <= Node.val <= 9
  • It is guaranteed that the list represents a number that does not have leading zeros.

二、分析

  • 此題是加法器的現作，只是改成 linked list 的型式。
  • 要注意進位時要新增新的 node。
  • 時間複雜度為 \(O(n)\)，若可利用原本的鏈表，空間複雜度可降為 \(O(1)\)。

三、解題

1. Recursion

  • Time complexity: \(O(n)\)
  • Space complexity: \(O(1)\)
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    return add(l1, l2, 0);
}
ListNode* add(ListNode* l1, ListNode* l2, int cin){     // 將 cin 設為 carry in
    l1->val += l2->val + cin;
    cin = l1->val / 10;     // 進位
    l1->val %= 10;
    if (l1->next || l2->next || cin != 0){      // 若有下一位數，或 carry in 不等於 0
        l1->next = add((l1->next == NULL ? new ListNode(0) : l1->next),
                       (l2->next == NULL ? new ListNode(0) : l2->next),
                        cin);
    }
    return l1;
}
}

2. Iteration

  • Time complexity: \(O(n)\)
  • Space complexity: \(O(1)\) dummy
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode* dummy = new ListNode(-1, l1);     // 設置一個 sentinel node
    ListNode* curr = dummy;     // 設置一個在當前位置前的節點來控制資料
    int cin = 0;
    while (l1 || l2 || cin > 0) {   // 當必定有下一位時
        // 借用 l1 或 l2，若兩者皆為空節點，則新建一個
        ListNode* tmp = l1 ? l1 : l2 : l2 : new ListNode(0);
        // 加法器
        tmp->val = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + cin;
        cin = tmp / 10;
        tmp->val %= 10;
        // 處理當 l1 為空結點的狀況
        if (!l1 && l2) {    // l2 不為空節點時，則借 l2 來用
            curr->next = l2;
        } else {        // 若 l1 跟 l2 都是空節點，建一個新的節點
            curr->next = tmp;
        }
        
        if (l1) l1 = l1->next;  // 前進一個節點
        if (l2) l2 = l2->next;    
        curr = curr->next;
    }
    return dummy->next;     // 記得回傳的是 sentinel->next
}

回目錄 Catalog