每日一題(LeetCode)----鏈表–兩數相加

1.題目（2. 兩數相加）

• 給你兩個 非空 的鏈表，表示兩個非負的整數。它們每位數字都是按照 逆序 的方式存儲的，并且每個節點只能存儲 一位 數字。

  請你將兩個數相加，并以相同形式返回一個表示和的鏈表。

  你可以假設除了數字 0 之外，這兩個數都不會以 0 開頭。

  示例 1：

  

  輸入：l1 = [2,4,3], l2 = [5,6,4]
  輸出：[7,0,8]
  解釋：342 + 465 = 807.
  

  示例 2：

  輸入：l1 = [0], l2 = [0]
  輸出：[0]
  

  示例 3：

  輸入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
  輸出：[8,9,9,9,0,0,0,1]
  

  提示：

  • 每個鏈表中的節點數在范圍 [1, 100] 內
  • 0 <= Node.val <= 9
  • 題目數據保證列表表示的數字不含前導零

2.解題思路

思路一

循環

1.先獲取兩個鏈表的長度，然后把較長鏈表作為我們的結果鏈表 2.創建一個記錄進位的變量，用兩個指針從頭開始遍歷兩個鏈表每次遍歷到的節點如果非空，那么把當前節點中的值和當前進位進行相加，如果和大于10，那么下一次的進位變為1，然后和減10，存到結果鏈表的對應節點中，一直遍歷直到遍歷完較長鏈表時結束，(為了之后我們添加新節點，所以遍歷到較長鏈表的結尾時，我們用tail指針保存一下較長鏈表的結尾) 3.然后我們查看當前進位是否為0，如果不為零，那我們新創建一個節點，接到結果鏈表的后面操作結束，如果為零，那么不需要新創建一個節點，操作結束 4.返回新鏈表的頭節點

思路二：遞歸

遞歸解法非常巧妙。

做遞歸題目一定要牢記「遞歸函數的定義」。

遞歸函數定義：addTwoNumbers 表示將兩個鏈表 l1 和 l2 相加得到的新鏈表； 遞歸終止條件：如果 l1 和 l2 有一個為空，則返回另外一個。 遞歸函數內容：

把兩個鏈表節點的值相加（結果記為 add ）。把 add 模 10 作為當前的鏈表節點的值。
把兩個鏈表的 next 節點相加。（注意：如果當前相加的結果 add>=10，需要把 next 節點相加得到的結果 + 1。）
遞歸解法妙在天然地處理好了兩個鏈表不一樣長、最終相加結果有進位的情況。

原作者：負雪明燭

鏈接：https://leetcode.cn/problems/add-two-numbers/

自己的理解：就是先從前到后先走一遍，算出所有的和作為答案，然后從后往前看有哪個和超過了10，超過了10就繼續向后遞歸，但是遞歸的對象變為當前進位和它的下一位和，到了遞歸的終止條件之后，就繼續向前返回

3.寫出代碼

思路一的代碼

class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {//先獲取兩個鏈表的長度int length1=0;int length2=0;ListNode* Temp1=l1;ListNode* Temp2=l2;int length=0;while(Temp1){length1++;Temp1=Temp1->next;}while(Temp2){length2++;Temp2=Temp2->next;}//判斷那個鏈表長作為我們的結果鏈表ListNode* res1=nullptr;ListNode* res2=nullptr;if(length1>=length2){length=length1;res1=l1;res2=l2;}else{length=length2;res1=l2;res2=l1;}Temp1=res1;Temp2=res2;int carry=0;//記錄進位的變量ListNode* Temp3=nullptr;//存的是較長鏈表的最后一個節點//兩個鏈表對應的節點進行相加while(length--){int sum=0;if(Temp1&&Temp2){sum=Temp1->val+Temp2->val+carry;}else{sum=Temp1->val+carry;}carry=0;if(sum>=10){carry++;sum=sum-10;Temp1->val=sum;}else{Temp1->val=sum;}if(Temp1->next==nullptr){Temp3=Temp1;}Temp1=Temp1->next;if(Temp2){Temp2=Temp2->next;}}if(carry>0){ListNode* node=new ListNode(carry);Temp3->next=node;}return res1;}
};

思路二的代碼

class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {if (!l1) return l2;if (!l2) return l1;int target = l1->val + l2->val;ListNode* res = new ListNode(target % 10);res->next = addTwoNumbers(l1->next, l2->next);if (target >= 10){res->next = addTwoNumbers(res->next, new ListNode(1));}delete l1, l2;return res;}
};

原作者：負雪明燭

鏈接：https://leetcode.cn/problems/add-two-numbers/