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.
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），表示兩個非負整數。這兩個整數以相反的順序存儲，每個節點包含一位數字。將這兩個整數相加並以連結串列的形式返回。
例如，輸入的連結串列為：
list1: 2 -> 4 -> 3 代表數字342
list2: 5 -> 6 -> 4 代表數字465
我們知道342+465=807
則返回的連結串列為：
7 -> 0 -> 8
建一個假節點(dummy node)作為新連結串列的起始節點
dummy -> NULL
初始化遍歷指針 curr 指向假節點(dummy node)
dummy -> NULL
curr
初始化進位 carry 為 0。
開始進行迴圈遍歷，將兩個連結串列對應節點的值相加，並加上進位 carry：
carry = 0 + 2 + 5 = 7
建一個新節點，節點值為和的個位數 7 % 10 = 7，並將其連接到新連結串列上：
dummy -> 7 -> NULL
curr
更新進位 carry，carry = 7 / 10 = 0。
===========================================================
向下移動 list1 和 list2 的指針，繼續處理下一個位數：
list1: 4 -> 3
list2: 6 -> 4
將兩個連結串列對應節點的值相加，並加上進位 carry
carry = 0 + 4 + 6 = 10
建一個新節點，節點值為和的個位數 10 % 10 = 0，並將其連接到新連結串列上
dummy -> 7 -> 0 -> NULL
curr
更新進位 carry，carry = 10 / 10 = 1。
===========================================================
向下移動 list1 和 list2 的指針，繼續處理下一個位數：
list1: 3
list2: 4
將兩個連結串列對應節點的值相加，並加上進位 carry
carry = 1 + 3 + 4 = 8
建一個新節點，節點值為和的個位數 8 % 10 = 8，並將其連接到新連結串列上：
dummy -> 7 -> 0 -> 8 -> NULL
curr
更新進位 carry，carry = 8 / 10 = 0。
===========================================================
向下移動 list1 和 list2 的指針，繼續處理下一個位數：
list1: NULL
list2: NULL
由於 list1 和 list2 都為空，迴圈結束。
檢查進位 carry，若不為 0，則創建一個新節點，節點值為進位值，並將其連接到新連結串列上：
dummy -> 7 -> 0 -> 8 -> NULL
curr
返回新連結串列的頭節點，即為相加結果：
result: 7 -> 0 -> 8 -> NULL
在此一樣要先建立一個dummy head
初始值隨意
可以使用迴圈來遍歷這兩個連結串列，同時對每個對應的節點進行相加操作，並構建一個新的連結串列作為結果。具體步驟如下：
Step1.初始化一個新的連結串列和一個遍歷指針（curr）指向新連結串列的頭節點。同時，初始化兩個遍歷指針（p1 和 p2）分別指向 list1 和 list2 的頭節點。
Step2.使用一個變量 carry 來保存進位，初始值為 0。
Step3.遍歷 list1 和 list2，直到兩者都為空。在每次遍歷中，分別獲取 p1 和 p2 的節點值（如果為空，則為 0），並計算當前位數的和：sum = p1->val + p2->val + carry。
Step4.將 sum 的個位數添加到新的連結串列中：curr->next = new ListNode(sum % 10)。
Step5.更新 carry，如果 sum 大於等於 10，則 carry 設為 1；否則設為 0。
Step6.將 p1 和 p2 同時向後移動一位：p1 = p1->next，p2 = p2->next。
Step7.如果 p1 或 p2 還有剩餘的節點，則繼續遍歷，重複步驟 3 到步驟 6。
Step8.如果 carry 的值為 1，則在新連結串列的尾部添加一個值為 1 的新節點：curr->next = new ListNode(1)。
返回新連結串列的頭節點：return dummy->next。
程式碼解法:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* dummy = new ListNode(0); ListNode* curr = dummy; int carry = 0; while (l1 || l2 || carry) { int sum = carry; if (l1) { sum += l1->val; l1 = l1->next; } if (l2) { sum += l2->val; l2 = l2->next; } carry = sum / 10; sum = sum % 10; curr->next = new ListNode(sum); curr = curr->next; } return dummy->next; } }; |
在此回傳是針對dummy的下一個節點回傳
Ref:
https://skyyen999.gitbooks.io/-leetcode-with-javascript/content/questions/2md.html
留言
張貼留言