LeetCode：0002（兩數(shù)之和）

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

算法思路

思路

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

?

偽代碼如下：

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

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);?????//指向下一節(jié)點
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};

轉(zhuǎn)載于:https://www.cnblogs.com/ywx123/p/9971567.html

總結(jié)

以上是生活随笔為你收集整理的Leetcode：0002（两数之和）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。