Lintcode 167. 链表求和 221. 链表求和 II 题解

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 题解的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。