167. 鏈表求和

描述

你有兩個用鏈表代表的整數，其中每個節點包含一個數字。數字存儲按照在原來整數中相反的順序，使得第一個數字位于鏈表的開頭。寫出一個函數將兩個整數相加，用鏈表形式返回和。

樣例

給出兩個鏈表?3->1->5->null?和?5->9->2->null，返回?8->0->8->null

思路：從左往右相加，考慮進位即可。一些細節一定要自己寫一遍才能體會

/*** Definition of singly-linked-list:* class ListNode {* public:* int val;* ListNode *next;* ListNode(int val) {* this->val = val;* this->next = NULL;* }* }*/class Solution { public:/*** @param l1: the first list* @param l2: the second list* @return: the sum list of l1 and l2 */ListNode * addLists(ListNode * l1, ListNode * l2) {// write your code hereListNode *cur1 = l1;ListNode *cur2 = l2;ListNode *res = new ListNode(-1);ListNode *res_cur = res;int flag = 0;while(cur1 || cur2){int sum = (cur1?cur1->val:0) + (cur2?cur2->val:0) + flag;ListNode *temp = new ListNode(sum%10);res_cur -> next = temp;res_cur = res_cur->next;flag = sum/10;cur1 = cur1?cur1->next:cur1;cur2 = cur2?cur2->next:cur2;}if(flag) res_cur->next = new ListNode(1);//最后的進位，易錯點return res->next;} };

?

?

?

221.?鏈表求和 II

描述

假定用一個鏈表表示兩個數，其中每個節點僅包含一個數字。假設這兩個數的數字順序排列，請設計一種方法將兩個數相加，并將其結果表現為鏈表的形式。

樣例

給出?6->1->7?+?2->9->5。即，617 + 295。

返回?9->1->2。即，912?。

思路：是上面題目的進階版，數字順序變了，自然考慮到翻轉鏈表再計算。

/*** Definition of singly-linked-list:* class ListNode {* public:* int val;* ListNode *next;* ListNode(int val) {* this->val = val;* this->next = NULL;* }* }*/class Solution { public:/*** @param l1: The first list.* @param l2: The second list.* @return: the sum list of l1 and l2.*/ListNode * addLists2(ListNode * l1, ListNode * l2) {// write your code hereListNode *l1_rev = reverseList(l1);ListNode *l2_rev = reverseList(l2);return reverseList(addLists(l1_rev,l2_rev));//最后別忘記翻回來}ListNode * reverseList(ListNode *l){　　　　//翻轉鏈表ListNode *res = new ListNode(-1);ListNode *cur = l;while(cur){ListNode * temp = cur->next;cur->next = res->next;res->next = cur;cur = temp;}return res->next;}ListNode * addLists(ListNode * l1, ListNode * l2) {//翻轉后的鏈表求和，同上// write your code hereListNode *cur1 = l1;ListNode *cur2 = l2;ListNode *res = new ListNode(-1);ListNode *res_cur = res;int flag = 0;while(cur1 || cur2){int sum = (cur1?cur1->val:0) + (cur2?cur2->val:0) + flag;ListNode *temp = new ListNode(sum%10);res_cur -> next = temp;res_cur = res_cur->next;flag = sum/10;cur1 = cur1?cur1->next:cur1;cur2 = cur2?cur2->next:cur2;}if(flag) res_cur->next = new ListNode(1);return res->next;} };

?

?

轉載于:https://www.cnblogs.com/J1ac/p/9092733.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的Lintcode 167. 链表求和 221. 链表求和 II 题解的全部內容，希望文章能夠幫你解決所遇到的問題。

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