本文主要是介绍算法题解记录15+++两数相加（百日筑基），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述：
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[7,0,8] 解释：342 + 465 = 807.
示例 2：
输入：l1 = [0], l2 = [0] 输出：[0]
示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 输出：[8,9,9,9,0,0,0,1]
提示：
- 每个链表中的节点数在范围
[1, 100]内 0 <= Node.val <= 9- 题目数据保证列表表示的数字不含前导零
解题准备：
1.了解链表：
链表是一种链式结构，其常用while进行遍历。
2.理解题意：
输入：题意有两个输入，链表l1的头节点l1，链表l2的头节点l2；；
数据：题目涉及的数据“倒序”存储在链表中，也就是对于123，链表中是3->2->1。
要求：返回一个同样格式的链表，其值为l1与l2相加
3.了解可能存在的基础操作：
首先，想要相加两个链表，得思考如何抽取出数据，因此大概率有遍历（查找）
第二，既然要返回一个链表，我们得新生一个链表（也许可以在原链表l1或l2上操作，不过十分不建议），因此，大概率存在添加。
总结，大概有查找、添加。
解题难点1分析：朴素的思路
从朴素的角度理解，这道题可能分为三步：
第一步，拿到链表l1、l2的数据。
第二步，二者求和，得到data。【该步比较简单不讲解】
第三步，对于data，生成新链表。
难点1：如何获得其数据？
从l1的角度，其每个结点的值为0到9，不过它们代表的数据不一致。
比如链表l1为3->2->1；
那么，3是个位数，2是十位数，1是百位数。
因此，我们需要一个数据len，保存位数的数据。假设len初始为0，那么伪代码有：
//伪代码
// l1:3->2->1;
int len=0;
int data=0;
while（l1!=null）{data += l1.val * Math.pow(10, len);l1=l1.next;
}经此，可以得到链表中存储的数据。
思考题：如果链表中的数据，超出了int，甚至long的存储限制怎么办？（下面解答。）
难点2：如何根据data，生成新链表？
假设新链表代表的数据，是data，如何根据data生成新链表？
要求是倒序排列，因此个数位在第一位，十位数在第二位，以此类推……
如何拿到个位数？
取余操作，也是比较经典的基本操作。
接着，我们借助一个len，可以很快生成新链表。伪代码如下：
// 伪代码
// 假设已经有data
ListNode result=new ListNode();
ListNode temp=result; // 避免头节点找不到while(true){temp.val=data%10;data=data/10;if(data>0){temp.next=new ListNode();temp=temp.next;}else{break;}
}return result;本解法，计算一次num1、一次num2，此时时间复杂度是O（n1+n2），又因为生成可能需要O（n1或n2【最大的】），所以总体为O（N）
解题难点2分析：更便捷的思路
链表的每一个节点，其值为0到9，那么两个链表相加，对于任何一位，其结果最多是0到18，也就是最多进一位。
如果把链表看成一个倒序的数组（或者直接看成数组），我们可以发现，把两个链表l1、l2对齐后，相加，只会有两种结果：值、值与进一位。
如果l1、l2同时开始，同步前进，有可能会出现l1的长度小于l2，此时遍历完l1后，l1就没有数据了。
因此，我们可能需要视情况补0，也就是认为，较小的那个链表，其后面全是0。
这样，就可以满足题意。
代码：
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode res, temp;boolean flag=false;int data=0;int n1, n2;res=new ListNode();temp=res;while(l1!=null||l2!=null){n1=l1==null?0:l1.val;n2=l2==null?0:l2.val;data=n1+n2;l1=l1==null?null:l1.next;l2=l2==null?null:l2.next;if(flag){data++;flag=false;}temp.val=data%10;if(data>=10){flag=true;}if(l1==null&&l2==null){break;}temp.next=new ListNode();temp=temp.next;}if(flag){temp.next=new ListNode();temp=temp.next;temp.val=1;}return res;}
}以上内容即我想分享的关于力扣热题15的一些知识。
我是蚊子码农，如有补充，欢迎在评论区留言。个人也是初学者，知识体系可能没有那么完善，希望各位多多指正，谢谢大家。
这篇关于算法题解记录15+++两数相加（百日筑基）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
