leetcode_2_两数相加
题目描述
给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。
请你将两个数相加,并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例 1:
1 | 输入:l1 = [2,4,3], l2 = [5,6,4] |
示例 2:
1 | 输入:l1 = [0], l2 = [0] |
示例 3:
1 | 输入:l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] |
提示:
- 每个链表中的节点数在范围 $[1, 100]$ 内
- $0 <= Node.val <= 9$
- 题目数据保证列表表示的数字不含前导零
解析
题目给出两个链表,由头节点顺序遍历得到的序列是一个数的逆序列,求两个链表所表示的两数之和。
我们可以新建一个结果链表res
,并设置一个工作指针last
。初始化,指向res
头节点。设置carry
记录当前进位数,初始化为0.
循环。遍历l1
,l2
两个链表
分为以下种种情况
l1!=null&&l2!=null
此时
l1.val
和l2.val
和carry
相加,(l1.val+l2.val+carry)%10
是当前位的数,(l1.val+l2.val+carry)/10
是当前进位的数。两者顺序不能变。l1
,l2
,last
,后移l1!=null&&l2==null
(l1.val+carry)%10
是当前位的数,(l1.val+carry)/10
是当前进位的数l1
,last
,后移l1==null&&l2!=null
(l2.val+carry)%10
是当前位的数,(l2.val+carry)/10
是当前进位的数l2
,last
,后移l1==null&&l2==null
这步是收尾工作,判断当前位carry是否为0,是则last.next==null,否则last.next.val=carry
这里仅需判断carry而无需判断高位的情况,因为不存在高位为0的情况
代码实现
1 | /* |
评论