Leetcode：0002（兩數之和）

LeetCode：0002（兩數之和）

題目描述：給定兩個非空鏈表來表示兩個非負整數。位數按照逆序方式存儲，它們的每個節點只存儲單個數字。將兩數相加返回一個新的鏈表。
你可以假設除了數字 0 之外，這兩個數字都不會以零開頭。
示例：
輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出：7 -> 0 -> 8
原因：342 + 465 = 807

算法思路

思路

算法
??就像你在紙上計算兩個數字的和那樣，我們首先從最低有效位也就是列表 和 的表頭開始相加。由于每位數字都應當處于 的范圍內，我們計算兩個數字的和時可能會出現“溢出”。例如，5 + 7 = 125+7=12。在這種情況下，我們會將當前位的數值設置為 2，并將進位 帶入下一次迭代。進位carry必定是0或1，這是因為兩個數字相加（考慮到進位）可能出現的最大和為 9 + 9 + 1 = 19。

?

偽代碼如下：

• 將當前結點初始化為返回列表的啞結點。
• 將進位 carry初始化為0。
• 將p和q分別初始化為列表和的頭部。
• 遍歷列表和直至到達它們的尾端。
  • 將x設為結點p的值。如果p已經到達$l1$的末尾，則將其值設置為0。
  • 將y設為結點q的值。如果q已經到達l2的末尾，則將其值設置為0。
  • 設定 $sum = x + y + carry$。
  • 更新進位的值，$carry = sum / 10$。
  • 創建一個數值為 (sum mod 10) 的新結點，并將其設置為當前結點的下一個結點，然后將當前結點前進到下一個結點。
  • 同時，將p和q前進到下一個結點。
  • 檢查$carry = 1$是否成立，如果成立，則向返回列表追加一個含有數字$11$的新結點。
    返回啞結點的下一個結點。
    解法

 1/**
 2?*?Definition?for?singly-linked?list.
 3?*?struct?ListNode?{
 4?*?????int?val;
 5?*?????ListNode?*next;
 6?*?????ListNode(int?x)?:?val(x),?next(NULL)?{}
 7?*?};
 8?*/
 9class?Solution?{
10public:
11????ListNode*?addTwoNumbers(ListNode*?l1,?ListNode*?l2)?{
12????????ListNode?*dummyHead?=?new?ListNode(0);
13????????ListNode?*cur?=?dummyHead;
14????????int?carry?=?0;??????????????????????????????//進位用
15????????while(l1?!=?NULL?||?l2?!=?NULL){
16????????????int?x?=?(l1?!=?NULL)???l1?->?val?:0;
17????????????int?y?=?(?l2?!=?NULL)???l2?->?val?:?0;
18????????????int?sum?=?carry?+?x?+?y;
19????????????carry?=?sum?/?10;?????????????????????????//進位
20????????????cur?->?next?=?new?ListNode(sum?%?10);?????//指向下一節點
21????????????cur?=?cur?->?next;
22????????????if(l1?!=?NULL)
23????????????????l1?=?l1->next;
24????????????if(l2?!=?NULL)
25????????????????l2?=?l2->next;
26????????}
27????????if(carry>0)
28????????????cur->next?=?new?ListNode(carry);????//加上進位
29????????return?dummyHead->next;
30????}
31};