兩種解法，第一種是在原有的兩個鏈表中選擇更長的那個作為結果返回，雖然節約了空間，但是增加了時間復雜度，而且沒有用到如何設置鏈表的增加與刪除，第二種看起來清爽很多，邏輯也清晰。

### 題目

給出兩個非空的鏈表用來表示兩個非負的整數。其中，它們各自的位數是按照逆序的方式存儲的，并且它們的每個節點只能存儲一位數字。

如果，我們將這兩個數相加起來，則會返回一個新的鏈表來表示它們的和。

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

示例：

輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出：7 -> 0 -> 8
原因：342 + 465 = 807

### 思路

首先計算出兩個鏈表分別的長度，然后將長度更長的那個作為存儲相加結果的鏈表，這樣可以少掉很多操作，然后從鏈表頭開始相加，就是注意一下進位的存儲以及處理就好了。

詳細的思路結合代碼寫在注釋里了，代碼雖然長，但其實是存在重復的，這個下次寫可以注意下，單獨提出一個函數來降低冗余。

### code

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/class Solution {public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {int l1_length=0;int l2_length=0;ListNode *p1=l1;ListNode *p2=l2;while(p1)//計算兩個鏈表的長度{l1_length++;p1=p1->next;}while(p2){l2_length++;p2=p2->next;}int jinwei=0;//存儲進位p1=l1;p2=l2;if(l1_length==0)//任何一個長度為0，都可以直接返回另外一個。return l2;if(l2_length==0)return l1;if(l1_length>l2_length)l1更長{ListNode *lastp1=p1;while(lastp1->next)//找到l1的最后一位。lastp1=lastp1->next;while(p1&&p2){p1->val+=p2->val+jinwei;//兩者相加，結果存儲在l1當中。jinwei=0;if(p1->val>=10)//如果結果大于10,那么需要求余并且進位。{jinwei=1;p1->val%=10;}p1=p1->next;p2=p2->next;}while(p1)//因為是l1更長，所以只有可能最后還剩下l1的鏈表節點，也有可能不剩下。{p1->val+=jinwei;//只用和進位相加了，l2已經計算結束了。jinwei=0;if(p1->val==10)//同理取余。{jinwei=1;p1->val=0;}p1=p1->next;}if(jinwei==1)//如果最后還多一個進位，那么需要把它加在l1的最后，這就是取l1尾部的原因，//因為p1肯定是已經到了l1尾部的后一個點，并且不能倒退，所以只能之前就遍歷一遍。{ListNode *new1=new ListNode(1);lastp1->next=new1;}return l1;}else if(l1_length<l2_length)//一樣的道理，只是用l2來返回。{ListNode *lastp2=p2;while(lastp2->next)lastp2=lastp2->next;while(p1&&p2){p2->val+=p1->val+jinwei;jinwei=0;if(p2->val>=10){jinwei=1;p2->val%=10;}p1=p1->next;p2=p2->next;}while(p2){p2->val+=jinwei;jinwei=0;if(p2->val==10){jinwei=1;p2->val=0;}p2=p2->next;}if(jinwei==1){ListNode *new1=new ListNode(1);lastp2->next=new1;}return l2;}else//這是兩者等長的情況。{ListNode *lastp1=l1;while(lastp1->next)lastp1=lastp1->next;while(p1&&p2){p1->val+=p2->val+jinwei;jinwei=0;if(p1->val>=10){jinwei=1;p1->val%=10;}p1=p1->next;p2=p2->next;}if(jinwei==1){ListNode *new1=new ListNode(1);lastp1->next=new1;}return l1;}return l1;}};

### 思路

上面那種方法是因為最開始不熟悉鏈表的建立這些，所以用的很笨的方法，下面這個快一點，不過感覺真正寫程序的時候要注意刪除，防止內存泄漏，看起來比第一個清爽很多。

### code

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/class Solution {public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* res=new ListNode(0);ListNode* p=res;int flag=0;while(l1||l2){int num=0;if(l1)num+=l1->val;if(l2)num+=l2->val;num=num+flag;flag=num/10;if(l1)l1=l1->next;if(l2)l2=l2->next;p->next=new ListNode(num%10);p=p->next; }if(flag==1)p->next=new ListNode(1);return res->next;}};

總結

以上是生活随笔為你收集整理的用递归计算一个数字每一位相加的结果。_leetcode 2 两数相加(c++)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。