Leetcode #2. Add Two Numbers
◎ 難度: Medium
◎ 題目:
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.
給你兩個 非空白的非負數(可能會有0)的linked lists,以降暮排序
每個節點都有一個0~9的個位數字
將每個節點數字分別加總後,以linked lists返回
返回的各節點值,僅限個位數字,進位數字加總到下一節點(需特別處理進位問題)
◎ Example 1:
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.
*** 第二個節點相加 (4+6=10),個位數為 0, 十位數字 加總到下一節點
所以,節點三 = 3+4+1(第二節點進位) = 8
◎ 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.
◎ 想法:
每個節點的值 最大=9
9+9=18,最大進位數字 =1
我們僅需要紀錄,前一節點加總後 是否有進位;有的話 這節點需 +1
再來須注意 輸入的兩個節點長度,可能是不相同的
然後,各節點取個位數字返回即可
◎ C++程式碼:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
////#define DEBUG 1
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
int sum = 0;
ListNode *l3 = new ListNode;
ListNode *node = l3;
while(l1 != NULL || l2 != NULL || sum > 0)
{
if(l1 != NULL)
{
sum += l1->val;
l1 = l1->next;
}
if(l2 != NULL)
{
sum += l2->val;
l2 = l2->next;
}
node->next = new ListNode(sum % 10);
node = node->next;
sum /= 10;
}
return l3->next;
}
};
沒有留言:
張貼留言