復習leetcode第二題：兩數相加

本文會給出筆者自己的解答（代碼較為冗余，其實就是屎山代碼）以及優秀代碼的解析

下圖是題目

解法1（筆者所使用的辦法）：?

解題思路：

以下思路是基于示例1（上圖）思考的

步驟1：因為該函數只傳來了兩個鏈表的首元結點指針，所以我們不難想到可以創建一個新鏈表來存放兩鏈表相加的內容

步驟2：由于我們最后需要返回新鏈表的首元結點指針，而新鏈表不斷創建以后，用于創建鏈表的指針也后移了，因此我們還需要創建一個指針phead，用作最后的函數返回

步驟3：題目給我們的結構體名稱為Listnode（在注釋行寫了），筆者覺得大小寫切換太麻煩了，因此這邊改成了listnode

步驟4：通過示例1我們也不難發現，我們需要使用循環語句來多次讓兩個鏈表的結點內容相加，并存放到新鏈表中；而循環的退出條件應該是l1鏈表和l2鏈表的所有結點的數據全部相加完了，即l1、l2同時為空指針。

上述步驟代碼如下：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode listnode;
listnode* buynode(int x) //用于創建新鏈表的函數{listnode* newnode = (listnode*)malloc(sizeof(listnode));newnode->val = x;newnode->next = NULL;return newnode;
}//l1首元結點指針      //l2首元結點指針
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) 
{int count=0;listnode* newnode=buynode(0); //創建一個新鏈表的首元結點，之后每次創建新鏈表都傳0值，因為只有給新鏈表結點0這個初值才不會影響結果//當然也并不是必須給新鏈表的結點賦初值，這里只是為了保險起見listnode* phead=newnode;while(l1||l2) //退出條件為兩個指針全為空指針{……;}return phead;
}

示例1的情況：

示例1中出現了兩數相加等于10的情況，最后l1、l2結點所對應的新鏈表結點留下來的數據為0，然后把 1這個數值進1位和后續結點數據內容相加，這也就導致了 4+3+1 = 8。但我們不難發現，l1、l2的結點數據相加最大值為18（即使加上1也只有19），因此只有可能把1這個數值進1位，不可能把1以外的數值進1位。?

因此我們可以進行一個分支語句，分為了最后l1、l2結點數據相加 大于等于10 和 小于等于9 的兩種情況；然后通過一個計數器count，來判斷是否需要對后一個結點數據加1

每次相加完，讓l1、l2、新鏈表都往后移動一位

代碼如下所示：

        //分為l1+l2 <=9 以及 l1+l2 >=10 兩種情況//<=9if((l1->val)+(l2->val)+count<=9) {newnode->val=(l1->val)+(l2->val)+count;count=0;}//>=10else{newnode->val=(l1->val)+(l2->val)+count-10;count=1;}l1=l1->next;l2=l2->next; newnode->next=buynode(0);newnode=newnode->next;

示例2的情況用示例1的代碼就能解決，此處不再講解。

示例3的情況：

該示例告訴我們，l1為空時，l2不一定為空；l2為空時，l1不一定為空。

因此，會有三種情況：分別是l1、l2都不為空，只有l1為空，只有l2為空。此處可以通過三條分支語句來解決。

當l1為空，l2不為空時，把l1繼續往后移動一位代碼會出錯（對空指針進行解引用操作），因此我們需要在不同的分支語句里面對不同情況進行不同的向后移位操作

而當把所有數據相加完，l1、l2都為空的時候，有可能count仍為1（示例3輸出里最后會出現一個1的原因），因此我們需要在整個循環語句后，解決這個問題。直接在新鏈表最后面加上一個結點，且最后一個結點數據域只可能為1（上文已經講解過只可能為1的原因）

代碼如下所示：

        if(l1&&l2) //兩指針都非空{//分為l1+l2 <=9 以及 l1+l2 >=10 兩種情況//<=9if((l1->val)+(l2->val)+count<=9) {newnode->val=(l1->val)+(l2->val)+count;count=0;}//>=10else{newnode->val=(l1->val)+(l2->val)+count-10;count=1;}l1=l1->next;l2=l2->next; }else if(l1) //l1還不為空的情況{if((l1->val)+count<=9){newnode->val=(l1->val)+count;count=0;}else{newnode->val=(l1->val)+count-10;count=1;}l1=l1->next; //為防止對空指針l2進行解引用操作}    else if(l2) //l2還不為空的情況{if((l2->val)+count<=9){newnode->val=(l2->val)+count;count=0;}else{newnode->val=(l2->val)+count-10;count=1;}l2=l2->next; //為防止對空指針l1進行解引用操作}  if(count==1) //兩個指針全都為空但count還是為1，是對示例3的解決{newnode->next=buynode(1); //直接在newnode指針最后面加上一個結點，且最后一個結點數據域只可能為1}

由于新鏈表一直要創建到l1、l2都為空，那么在循環語句（循環語句退出條件為l1、l2都為空）里的新鏈表創建就不需要加以限制了呢？

答：如果不加以限制，會出現下圖的情況，這是由于在最后一次l1、l2結點數據相加并放入新鏈表以后，還會再進行一次新鏈表的結點創建

解決方法：

把新鏈表的首元結點的創建放在循環語句里面，并且在第一次創建新鏈表的結點時，把該結點賦給phead，并且所有操作都放在l1、l2結點數據相加之前
在循環語句末尾，給新鏈表的創建加上一條if語句，當l1、l2全為空指針，不再進行結點創建工作（筆者在此使用的）

        if(l1||l2) //只有兩指針還有需要存入的數據再開辟新的空間，如果都已經存放完畢，那么就無需再開辟新的{newnode->next=buynode(0);newnode=newnode->next;}

解法1全部代碼展示：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode listnode;
listnode* buynode(int x){listnode* newnode = (listnode*)malloc(sizeof(listnode));newnode->val = x;newnode->next = NULL;return newnode;
}//l1首元結點指針      //l2首元結點指針
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) 
{int count=0;listnode* newnode=buynode(0); //創建一個新鏈表的首元結點listnode* phead=newnode;while(l1||l2) //退出條件為兩個指針全為空{if(l1&&l2) //兩指針都非空{//分為l1+l2 <=9 以及 l1+l2 >=10 兩種情況//<=9if((l1->val)+(l2->val)+count<=9) {newnode->val=(l1->val)+(l2->val)+count;count=0;}//>=10else{newnode->val=(l1->val)+(l2->val)+count-10;count=1;}l1=l1->next;l2=l2->next; }else if(l1) //l1還不為空的情況{if((l1->val)+count<=9){newnode->val=(l1->val)+count;count=0;}else{newnode->val=(l1->val)+count-10;count=1;}l1=l1->next; //為防止對空指針l2進行解引用操作}    else if(l2) //l2還不為空的情況{if((l2->val)+count<=9){newnode->val=(l2->val)+count;count=0;}else{newnode->val=(l2->val)+count-10;count=1;}l2=l2->next; //為防止對空指針l1進行解引用操作}    if(l1||l2) //只有兩指針還有需要存入的數據再開辟新的空間，如果都已經存放完畢，那么就無需再開辟新的{newnode->next=buynode(0);newnode=newnode->next;}}if(count==1) //兩個指針全都為空但count還是為1，是對示例3的解決{newnode->next=buynode(1); //直接在newnode指針最后面加上一個結點，且最后一個結點數據域只可能為1}return phead;
}

解法2（優秀代碼）：
?

下面的代碼是leetcode官方給的C語言題解，好漂亮的代碼！

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {struct ListNode *head = NULL, *tail = NULL;int carry = 0;while (l1 || l2) {int n1 = l1 ? l1->val : 0;int n2 = l2 ? l2->val : 0;int sum = n1 + n2 + carry;if (!head) {head = tail = malloc(sizeof(struct ListNode));tail->val = sum % 10;tail->next = NULL;} else {tail->next = malloc(sizeof(struct ListNode));tail->next->val = sum % 10;tail = tail->next;tail->next = NULL;}carry = sum / 10;if (l1) {l1 = l1->next;}if (l2) {l2 = l2->next;}}if (carry > 0) {tail->next = malloc(sizeof(struct ListNode));tail->next->val = carry;tail->next->next = NULL;}return head;
}

上述代碼解釋：

官方題解也是通過創建一個新鏈表，然后解決問題

首先創建了兩個指針，一個指向了首元結點（用作返回），一個指向了尾元結點（用作存放數據）；carry和我代碼中的count一樣，都是保存多出來的那個1的

循環語句退出條件、分支語句的寫法此處省略

l1 ? l1->val : 0 --->該操作符的作用：l1不為空指針，就留下l1的值；l1為空指針，就留下0

l2 ? l2->val : 0 --->作用同上

sum：就是l1、l2的結點數據（還有carry）相加后結果

!head：如果頭指針為空指針為真（首元結點的創建，和首元結點地址的保留）

sum%10：對10取余

sum/10：整型相除

進行完對新鏈表的賦值操作以后，讓新鏈表的尾元結點指針指向空指針，等待下一次使用

最后如果carry依舊為1，那么再開辟一個結點空間存放，最后返回head指針