Leecode第二題：兩數相加
Leecode2:兩數相加
先看題目 ：
給你兩個 非空 的鏈表，表示兩個非負的整數。它們每位數字都是按照 逆序 的方式存儲的，並且每個節點只能存儲 一位 數字。
請你將兩個數相加，並以相同形式返回一個表示和的鏈表。
你可以假設除了數字 0 之外，這兩個數都不會以 0 開頭。
來源：力扣（LeetCode）
鏈接：//leetcode-cn.com/problems/add-two-numbers
著作權歸領扣網路所有。商業轉載請聯繫官方授權，非商業轉載請註明出處。
具體詳情可以點進鏈接 題目這裡就不做多餘的解釋了
題目分析
注意看提示
提示：
每個鏈表中的節點數在範圍 [1, 100] 內
0 <= Node.val <= 9
題目數據保證列表表示的數字不含前導零
說明沒有空鏈表 同時 肯定會越界
ok 我們就不能採用普通的辦法了
程式碼
ok 我們看程式碼：
先看一個比較容易理解的
先取出數據，後計算結果，在組合答案並返回
int a[101];
int b[101];// 初始化 數組
int End[102];// 最後的結果數組
int i;
for(i=0;i<101;i++)
{
a[i]=b[i]=End[i]=0;// 初始化
}
// 我們先算出結果 然後將其寫入結構體 然後返回
i=0;
ListNode * l=l1;
while (l) {
a[i++]=l->val;
l=l->next;// 取出l1
}
l=l2;
int aLength=i;
i=0;
while (l) {
b[i++]=l->val;
l=l->next;// 取出l2
}
int bLength=i;
int Cout=0;// 是否進位
int endLength=aLength >bLength? aLength :bLength;// 取最長的長度
for (i=0; i<endLength; i++) {
//進位位
Cout=a[i]+b[i]+Cout;
End[i]=Cout%10;;
Cout/=10;
}
if (Cout>0) {// 最高位是否發生進位 進位長度加一
End[endLength]=Cout;
endLength++;
}
ListNode *List =new ListNode;
l=List;
l->val=End[0];// 先把第一位放進去
for(i=1;i<endLength;i++)
{
l->next=new ListNode;
l=l->next;
l->val=End[i];
l->next=NULL;
}
// cout << endl;// 輸出驗證
l=List;
// while (l) {
// cout << l->val << "->";
// l=l->next;
// }
return List;
看一下結果：
執行用時: 52 ms
記憶體消耗: 69.4 MB
不過這個程式碼的效率可能會比較低 ： 超越了20%的提交記錄，不過這個更容易看懂
看一個更簡便的方式 ，
int Cout =0;
ListNode * Lis = new ListNode;
ListNode * l=Lis;
while(l1 && l2){
Lis->next=new ListNode;
Lis=Lis->next;
Cout=Cout+l1->val+l2->val;
l1=l1->next;
l2=l2->next;
Lis->val=Cout%10;
Cout/=10;
}
while (l1) {
Cout+=l1->val;
l1=l1->next;
Lis->next=new ListNode;
Lis=Lis->next;
Lis->val=Cout%10;
Cout/=10;
}
while (l2) {
Cout+=l2->val;
l2=l2->next;
Lis->next=new ListNode;
Lis=Lis->next;
Lis->val=Cout%10;
Cout/=10;
}
if(Cout>0){
Lis->next =new ListNode;
Lis = Lis->next;
Lis->val=Cout;
Lis->next=NULL;
}
return l->next;
這個就不加註釋了 ，和上面原理差不多。
這個的結果：
執行結果：
執行結果：
通過
執行用時：32 ms, 在所有 C++ 提交中擊敗了86.94%的用戶記憶體消耗：69.6 MB, 在所有 C++ 提交中擊敗了14.75%的用戶
時間上就會快很多 不過也跟處理機有關，就上面這個程式碼，我交了好多次，還出現過52ms的情況
總結
這裡主要考察大數加法 原理根小時候學的加法一模一樣 ，相信看過上面程式碼就理解個差不多了，就不多解釋了。
