题目描述
输入参数：
表示两个非负的整数。，。
- 两个非空的链表
- 节点数量范围:[1, 100]
- 0 <= 节点数值 <= 9
题目逻辑：
- 返回请你两个链表内的元素对应位置进行相加，并以相同形式返回一个表示和的链表
输出结果：
- 返回一个表示两数和的链表
特别说明：
- 规则：它们每位数字都是按照逆序的方式存储的
- 规则：并且每个节点只能存储一位数字
- 规则：除了数字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] 复制代码
思路分析
我们使用变量来跟踪进位，并从包含最低有效位的表头开始模拟逐位相加的过程。
就像你在纸上计算两个数字的和那样，我们计算两个数字的和时可能会出现 “溢出”。
- 例如，5 + 7 = 12。在这种情况下，我们会将当前位的数值设置为 2，并将进位 carry = 1带入下一次迭代。
- 进位 carry必定是 0 或 1，这是因为两个数字相加（考虑到进位）可能出现的最大和为 9 + 9 + 1 = 19。
值得注意的 两个链表的长度不一定相同 故有可能存在一个链表走完 另一个链表还未走完的情况，故走完的链表还要将其值赋值为0，直至两个链表都走到Null。
AC代码
实现方法1
class Solution { /* * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode p=new ListNode(-1); //创建一个新的结点 ListNode res=p; int st=0;//标志位 while(l1!=null || l2!=null){ //当l1为空结点的时候 防止取空 赋值为0 便于高位相加 同理l2 int x= l1==null? 0:l1.val; int y= l2==null ?0:l2.val; //相加后的值 int temp=(x+y+st); //个位上的数字 int value=temp%10; //产生新结点 进行拼接 ListNode q=new ListNode(value); p.next=q; p=p.next; //得到进位 st=temp>=10?1:0; //当结点为null不前进 l1= l1==null? l1:l1.next; l2= l2==null? l2:l2.next; } if(st==1){ ListNode q=new ListNode(st); p.next=q; } return res.next; } } 复制代码
实现方法2（简易版）
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { int carry = 0; ListNode dummy = new ListNode(-1); ListNode cur = dummy; while (l1 != null || l2 != null || carry != 0) { int s = (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val) + carry; carry = s / 10; cur.next = new ListNode(s % 10); cur = cur.next; l1 = l1 == null ? null : l1.next; l2 = l2 == null ? null : l2.next; } return dummy.next; } } 复制代码
总结：
- 逻辑的算法实现较为简单：主要思路就是依靠遍历链表，所以大家一定要对链表的结构和遍历以及维护的机制有着比较熟悉的概念。
- 需要多多考虑相关进位方式考虑进位向前以为进行处理。【0,19】
- 如果存在两个链表的长度不一致，要考虑null的处理，转换为0的处理机制。
