題目
給出兩個 非空 的鏈表用來表示兩個非負的整數(shù)馆蠕。其中，它們各自的位數(shù)是按照 逆序 的方式存儲的播赁，并且它們的每個節(jié)點只能存儲 一位 數(shù)字。
如果容为，我們將這兩個數(shù)相加起來，則會返回一個新的鏈表來表示它們的和坎背。
您可以假設除了數(shù)字 0 之外，這兩個數(shù)都不會以 0 開頭抬纸。
示例：
輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出：7 -> 0 -> 8
原因：342 + 465 = 807
解法一(我的思路)
思路：
將兩個鏈表代表的數(shù)字給表示出來，再將其求和耿戚，將將求和結果按照逆序的鏈表形式輸出即可！
/**
* 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 sum = 0;
int temp_i=1;
ListNode *temp = l1;
do{
sum += temp->val*temp_i;
temp_i = temp_i*10;
temp = temp->next;
}while(temp!=NULL);
temp = l2;
temp_i = 1;
do{
sum += temp->val*temp_i;
temp_i = temp_i*10;
temp = temp->next;
}while(temp!=NULL);
// 計算完成求和 開始創(chuàng)建新的鏈表 用來存放新的數(shù)據(jù)
ListNode * p = new ListNode(0);
ListNode * q;// 用來移動新生成的鏈表
q = p;
int num = 0;
num = sum % 10;
sum = sum / 10;
p->val = num;
do{
ListNode *newNode = new ListNode(0); // 創(chuàng)建新的節(jié)點
if(sum>0) break;
int num = 0;
num = sum % 10;
sum = sum / 10;
// 給臨時節(jié)點賦值
newNode->val = num;
newNode->next = NULL;
q->next = newNode; //將臨時節(jié)點賦值給移動的鏈表(指向新的鏈表)
q = newNode; // 此時移動的鏈表需要移動到當前節(jié)點上來
}while(sum>0);
return p;
}
};
在執(zhí)行代碼上計算結果與預期的結果一致坛猪，但是提交代碼時墅茉，老是提示錯誤呜呐？ 我開始絕望了。執(zhí)行代碼的時間4ms洋机，但是提交結果會出現(xiàn)錯誤洋魂？
錯誤提示為：
Line 28: Char 29: runtime error: signed integer overflow: 1000000000 * 9 cannot be represented in type 'int' (solution.cpp)
始終沒有找到錯誤的原因？ 但是覺得自己的思路是對的副砍！ 所以就沒有糾結這個問題，查看評論中網(wǎng)友給的答案豁翎？
解法二(自己的思路二)
思路：
由于對于該數(shù)據(jù)表示的單鏈表而言，其表示的第一個數(shù)字代表整數(shù)的個位數(shù)谨垃，其表示的第二位代表整數(shù)的十位數(shù)，以此類推刘陶。牢撼。。
同理另外一個數(shù)也是這樣表示的熏版，所以當兩個數(shù)字相加時捍掺，就是個位相加，遇到大于10挺勿，進一位即可喂柒，即可以在對鏈表遍歷的同時計算出最終的結果。
(需要考慮兩個鏈表不一樣長的問題灾杰！)
/**
* 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 *result = new ListNode(0); //存放結果的鏈表
ListNode *p1 ,*p2; //分別指向兩個相加的鏈表
ListNode *temp ; // 臨時節(jié)點 存放臨時數(shù)據(jù)
temp = result;
p1 = l1 , p2 = l2;
int z = 0; // 用來表示最終相同位數(shù)求和有沒有超過10的
while(p1!=NULL || p2!=NULL){ //當兩個指針都為空跳出來(思想差不多 不過后面參考了答案)
// 用這種方式可以避免其判斷 兩個鏈表之間的長度問題 當一個鏈表到頭了艳吠，用0表示后面位數(shù)
int x = (p1!=NULL) ? p1->val : 0 ;
int y = (p2!=NULL) ? p2->val : 0 ;
if(p1) p1 = p1->next;
if(p2) p2 = p2->next;
int sum = z + x+y;
z = sum /10; // 用來記錄大于10的位數(shù)(進一位則會記錄下來)
temp->next = new ListNode( sum % 10 );
temp = temp->next;
}
// 當兩者都已經(jīng)為空 看最后一位有沒有超過10的值
if(z>0) temp->next = new ListNode(z);
return result->next;
}
};
與答案的思想相同，但好像最后有參考答案怎么寫的昭娩，雖然用的是java語言凛篙，因為覺得他寫的會比我自己寫的更簡潔一點，但是后面還是盡量少的參考答案吧＠该臁Ｐ！迈嘹！
中間有發(fā)現(xiàn)出現(xiàn)錯誤是削彬，時間超時，后面檢查發(fā)現(xiàn)代碼錯誤Ｐ阒佟融痛！ 所以一般不會出現(xiàn)超時的現(xiàn)象！
結果： 時間 40ms 97.14%. 內(nèi)存 19.2M 37.42%
解答三 (網(wǎng)友答案1)
使用了遞歸的思想神僵，效率挺高的雁刷！
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
return addByBit(l1, l2, 0);
}
ListNode* addByBit(ListNode* l1, ListNode* l2, int carry) {
if (l1 == NULL) l1 = new ListNode(0);
if (l2 == NULL) l2 = new ListNode(0);
ListNode *l = new ListNode((l1->val + l2->val + carry) % 10);
carry = (l1->val + l2->val + carry) / 10;
if(l1->next != NULL || l2->next != NULL || carry == 1) {
l->next = addByBit(l1->next, l2->next, carry);
}
return l;
}
};
時間： 40ms
內(nèi)存: 19.6M
解答四 (網(wǎng)友答案2)
主要的套路跟我第二個套路是一樣的。
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode *ans = new ListNode(0), *t1=l1, *t2=l2;
ListNode *anshead=ans;
int carry=0;
while(t1||t2){
if(t1){
carry+= t1->val;
t1 = t1->next;
}
if(t2){
carry+= t2->val;
t2 = t2->next;
}
ans->val = carry%10;
carry /= 10;
if(t1||t2||carry){
ans->next = new ListNode(carry);
ans = ans->next;
}
}
return anshead;
}
};
時間：44ms
內(nèi)存： 19.2M
問題：
使用鏈表的操作不太熟悉保礼，對鏈表的使用掌握的不夠沛励！
學習鏈表知識:
鏈表主要包括兩個方面:
數(shù)據(jù)域 和 指針域
- 單鏈表節(jié)點信息包括:
數(shù)據(jù)域 : 用于存儲數(shù)據(jù)元素的值
指針域(鏈域)： 用于存放下一個節(jié)點地址或者指向后面節(jié)點的指針
struct Node{
int val; //數(shù)據(jù)域
Node *next; //指針域
}
具體參考鏈接...
參考鏈接:
