1.題目：兩個(gè)非負(fù)整數(shù)以逆序形式存儲(chǔ)在兩個(gè)鏈表，計(jì)算他們的和并同樣以逆序形式存進(jìn)鏈表并返回。

我一開始的思路是把這兩條鏈的數(shù)按位數(shù)乘10完整提出來，然后相加，再依次取位數(shù)對應(yīng)數(shù)字存進(jìn)鏈里，返回。
直到他給了我這么一個(gè)測試數(shù)據(jù)，我才明白它用鏈表傳參的目的。

然后我搜了一下long long的取值范圍：
-9223372036854775808-9223372036854775807
（即-2^63 - 2^63-1）
以及unsigned long： 0-1844674407370955161
（即0 - 2^64-1）

而這個(gè)測試數(shù)據(jù)起碼有30位數(shù)！
所以完整提出來相加是不可能的了。

然后到第二個(gè)思路：
兩個(gè)指針同時(shí)在對應(yīng)的相同位置遍歷兩條鏈list1和list2，把當(dāng)前遍歷到的數(shù)拿出來相加，>=10則拋出進(jìn)位數(shù)cnum=1，結(jié)果放到新增空間并尾插到新鏈，遍歷繼續(xù)。

這只是正常的情況，那么特殊的情況還有什么呢？
( [ ]內(nèi)代表數(shù)字在鏈表里的順序)

一長一短不進(jìn)位：[0006]+[003]
（6000+300）

一長一短進(jìn)位到最后：[99]+[9999]
（99+9999=10098）

一長一短進(jìn)位，但中途結(jié)束：[99]+[24912]
（99+21942=22041）

同長同短，但遍歷的最后一組數(shù)會(huì)進(jìn)位1：
[5]+[5]（5+5=10）

**對于一長一短的情況，我的思路是：
因?yàn)楸闅v條件是p和q同時(shí)不為NULL，此時(shí)的遍歷已經(jīng)斷掉，但仍有p!=NULL或者q!=NULL。
（下面以p!=NULL為例子）
先定義新指針k，記錄此時(shí)p的位置。

一.若此時(shí)進(jìn)位數(shù)cnum為0：
將k直接連接到returnlist的尾端。

二.若此時(shí)進(jìn)位數(shù)cnum為1：
則p繼續(xù)遍歷list剩下部分，每遍歷一次拋出cnum的值，直到cnum等于0，遍歷停止。
在此條件下（cnum為1），若遍歷在最后一個(gè)數(shù)前停止，將k連接到returnlist的尾端；若在最后一個(gè)數(shù)的位置停止，則新增空間將其值設(shè)為1，連接到list1尾部，再將k連接到returnlist的尾端。

**同長同短，遍歷最后一組數(shù)據(jù)進(jìn)位1：
直接新增空間設(shè)置其值為1，連接到新鏈表尾部。

下面貼代碼：
思路1（局限于長整型數(shù)據(jù)類型范圍內(nèi)）：

class Solution { public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {long long x1 = 0, x2 = 0, count=1,ans = 0;ListNode* p;p = l1; /*指向鏈1的第1個(gè)節(jié)點(diǎn)*/while (p != NULL) { /*做循環(huán)，讀取x1的值*/x1 += (p->val * count);p = p->next;count *= 10;}count = 1; /*結(jié)束count置一*/p = l2; /*指向鏈2的第1個(gè)節(jié)點(diǎn)*/while (p != NULL) { /*做循環(huán)，讀取x2的值*/x2 += (p->val * count);p = p->next;count *= 10;}ans = x1 + x2;long long tool = ans, flag = 0;do { /*整除法獲取結(jié)果ans的位數(shù)*/tool =tool/10;flag++;} while (tool != 0);ListNode* answer = new ListNode;answer->next = NULL;count = 1;for (int i = 1; i < flag; i++) count *= 10; /*根據(jù)位數(shù)建立'取余法'的變量值*/for (int i = 0; i < flag; i++) { /*將結(jié)果頭插入鏈*/int part =ans / count;ans = ans - part * count;p = new ListNode;p->val = part;p->next = answer->next;answer->next = p;count /= 10;}answer=answer->next;return answer;} };

思路一寫了好久也想貼一下，原諒我的菜 ╮(╯﹏╰）╭

思路二（正確解法）：

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* }；*/class Solution { public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* answer=new ListNode, * p = l1, * q = l2,*k=NULL,*o=NULL;answer->next = NULL;ListNode *New, * flag=answer;int ans = 0,judge=0;while (p != NULL && q != NULL) { /*從鏈頭到尾 對l1和l2每個(gè)對應(yīng)節(jié)點(diǎn)做加法*/if (judge==1) { /*如果上兩個(gè)數(shù)有進(jìn)位，則加上1*/if ((p->val+q->val+judge)>=10) {ans = (p->val + q->val+judge) % 10;judge= 1;}if ((p->val + q->val+judge) < 10) {ans = p->val + q->val+judge;judge = 0;}}else {if ((p->val + q->val) >= 10) {ans = (p->val + q->val) % 10;judge = 1;}if ((p->val + q->val) < 10) {ans = p->val + q->val;judge = 0;}}New = new ListNode;New->val = ans;New->next = flag->next; /*尾插法，flag->next永遠(yuǎn)是NULL*/flag->next = New;flag = flag->next;p = p->next; q = q->next;/*p，q遍歷*/}if (p == NULL && q == NULL&&judge==1) {New = new ListNode;New->val = 1;New->next = NULL;flag->next = New;}if (p == NULL&&q!=NULL) { /*一長一短，q還沒斷*/k = q;if (judge == 0)flag->next = k;if (judge == 1) {while (q != NULL && judge == 1) {if ((q->val + judge) >= 10) {q->val = (q->val + judge) % 10;judge = 1;}else {q->val = q->val + judge;judge = 0;}o = q;q = q->next;}if (q == NULL && judge == 1) {New = new ListNode;New->val = 1;New->next = NULL;o->next = New;}flag->next = k;}}if (q == NULL && p != NULL) {/*一長一短，p還沒斷*/k = p;if (judge == 0)flag->next = k;if (judge == 1) {while (p != NULL && judge == 1) {if ((p->val + judge) >= 10) {p->val = (p->val + judge) % 10;judge = 1;}else {p->val = p->val + judge;judge = 0;}o = p;p = p->next;}if (p == NULL && judge == 1) {New = new ListNode;New->val = 1;New->next = NULL;o->next = New;}flag->next = k;}}answer = answer->next;/*去頭（我個(gè)人認(rèn)為去不去都可以）*/return answer;} };

小結(jié)：
這個(gè)題目的思路對的話，再把每種情況想清楚就OK，運(yùn)用一些簡單的if和else語句，還有單鏈表的尾插法與頭插法。
網(wǎng)上有更優(yōu)的解法，輕噴。

總結(jié)

以上是生活随笔為你收集整理的两个长整数的相加的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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