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:
- 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)\)
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
}