做水晶接单在哪个网站接,如何制作个人公众号,四核网站建设,一键生成网站两种解法#xff0c;第一种是在原有的两个链表中选择更长的那个作为结果返回#xff0c;虽然节约了空间#xff0c;但是增加了时间复杂度#xff0c;而且没有用到如何设置链表的增加与删除#xff0c;第二种看起来清爽很多#xff0c;逻辑也清晰。### 题目给出两个非空的… 两种解法第一种是在原有的两个链表中选择更长的那个作为结果返回虽然节约了空间但是增加了时间复杂度而且没有用到如何设置链表的增加与删除第二种看起来清爽很多逻辑也清晰。### 题目给出两个非空的链表用来表示两个非负的整数。其中它们各自的位数是按照逆序的方式存储的并且它们的每个节点只能存储一位数字。如果我们将这两个数相加起来则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外这两个数都不会以 0 开头。示例输入(2 - 4 - 3) (5 - 6 - 4)输出7 - 0 - 8原因342 465 807### 思路首先计算出两个链表分别的长度然后将长度更长的那个作为存储相加结果的链表这样可以少掉很多操作然后从链表头开始相加就是注意一下进位的存储以及处理就好了。详细的思路结合代码写在注释里了代码虽然长但其实是存在重复的这个下次写可以注意下单独提出一个函数来降低冗余。### code /*** 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 l1_length0;int l2_length0;ListNode *p1l1;ListNode *p2l2;while(p1)//计算两个链表的长度{l1_length;p1p1-next;}while(p2){l2_length;p2p2-next;}int jinwei0;//存储进位p1l1;p2l2;if(l1_length0)//任何一个长度为0都可以直接返回另外一个。return l2;if(l2_length0)return l1;if(l1_lengthl2_length)l1更长{ListNode *lastp1p1;while(lastp1-next)//找到l1的最后一位。lastp1lastp1-next;while(p1p2){p1-valp2-valjinwei;//两者相加结果存储在l1当中。jinwei0;if(p1-val10)//如果结果大于10,那么需要求余并且进位。{jinwei1;p1-val%10;}p1p1-next;p2p2-next;}while(p1)//因为是l1更长所以只有可能最后还剩下l1的链表节点也有可能不剩下。{p1-valjinwei;//只用和进位相加了l2已经计算结束了。jinwei0;if(p1-val10)//同理取余。{jinwei1;p1-val0;}p1p1-next;}if(jinwei1)//如果最后还多一个进位那么需要把它加在l1的最后这就是取l1尾部的原因//因为p1肯定是已经到了l1尾部的后一个点并且不能倒退所以只能之前就遍历一遍。{ListNode *new1new ListNode(1);lastp1-nextnew1;}return l1;}else if(l1_lengthl2_length)//一样的道理只是用l2来返回。{ListNode *lastp2p2;while(lastp2-next)lastp2lastp2-next;while(p1p2){p2-valp1-valjinwei;jinwei0;if(p2-val10){jinwei1;p2-val%10;}p1p1-next;p2p2-next;}while(p2){p2-valjinwei;jinwei0;if(p2-val10){jinwei1;p2-val0;}p2p2-next;}if(jinwei1){ListNode *new1new ListNode(1);lastp2-nextnew1;}return l2;}else//这是两者等长的情况。{ListNode *lastp1l1;while(lastp1-next)lastp1lastp1-next;while(p1p2){p1-valp2-valjinwei;jinwei0;if(p1-val10){jinwei1;p1-val%10;}p1p1-next;p2p2-next;}if(jinwei1){ListNode *new1new ListNode(1);lastp1-nextnew1;}return l1;}return l1;}};### 思路上面那种方法是因为最开始不熟悉链表的建立这些所以用的很笨的方法下面这个快一点不过感觉真正写程序的时候要注意删除防止内存泄漏看起来比第一个清爽很多。### code /*** 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* resnew ListNode(0);ListNode* pres;int flag0;while(l1||l2){int num0;if(l1)numl1-val;if(l2)numl2-val;numnumflag;flagnum/10;if(l1)l1l1-next;if(l2)l2l2-next;p-nextnew ListNode(num%10);pp-next; }if(flag1)p-nextnew ListNode(1);return res-next;}};
