题目描述
给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。
请你将两个数相加,并以相同形式返回一个表示和的链表。
你可以假设除了数字 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]
思路介绍
首先链表与数组不同,我们无法在常量时间内访问单链表中的随机元素。如果我们想要获得第 i 个元素,我们必须从头结点逐个遍历。题目说明是逆序的方式,链表第一个数字即为个位,循环遍历至链表最后一位,选择使用while循环的方式进行遍历,只要l1,l2不为空或者carry不为零,一直重复操作。
其次需要考虑到数字相加进位的情况,
1.小于10,不需要进位 2.大于等于10,最多只需要进一位计算求进位和余数。
如果两个链表的长度不同,则可以认为长度短的链表的后面有若干个 00
存在一个链表next不是空,然后将指针指向下一个值,对下一个节点处理。
当链表节点都为空之后,别忘了对进位进行判断,如果最后还有进位的话,增加一个节点
代码
//root存放结果,cursor为root的尾指针
ListNode root = new ListNode(0);
ListNode cursor = root;
int jinwei = 0; //进位
while (l1!=null||l2!=null|| jinwei!=0){
//int s1 = l1.val;
//int s2 = l2.val;
//如果其中有一个到达结尾了,那么这个链表这一位的的数字就为0。
int s1 = l1!=null?l1.val:0;
int s2 = l2!=null?l2.val:0;
//两个链表的两位相加
int sum = s1+s2+jinwei;
jinwei = sum /10;
int yushu = sum%10;
ListNode sumNode = new ListNode(yushu);
//创建一个节点接入root后面
cursor.next = sumNode;
cursor = sumNode;
if(l1 != null) l1 = l1.next;
if(l2 != null) l2 = l2.next;
}
return root.next;
总结
此题不算难,主要需要考虑:
1.链表长度不相等的情况下需要补齐链表取零,
2.两个数相加进位的问题
3.链表遍历结束后有进位的情况,比较容易遗忘