两数相加
给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。
请你将两个数相加,并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外,这两个数都不会以 0 开头。
ListNode
1 | //Definition for singly-linked list. |
示例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:
图示2:
提示:
- 每个链表中的节点数在范围
[1, 100]
内 0 <= Node.val <= 9
- 题目数据保证列表表示的数字不含前导零
Related Topics
- 递归
- 链表
- 数学
链表转值计算
遇到这种链表的题,第一步就是将逻辑图画出来
经过观察可知,链表的第一位表示该数字的个位,第二位代表该数字的十位,以此类推。
我第一个想到的解题思路就是
1、将链表表示的数字算出来
2、将两个数字加起来
3、用该数字构建出来结果链表并返回
示例代码
1 | class Solution { |
来算一下long
的最大值是多少
long
在Java
里面使用8个字节也就是64位,最大值也就是2^64-1,也就是9_223_372_036_854_775_807
此方法乍一看确实没问题
但是题目提示有以下要求
测试的时候可能会出现100位的数字,long
类型最大值远远不够
当链表很长的时候,该方法就会超时并且发生溢出错误
递归
现在有两个链表,要清楚两点
1、两个链表的长度不一定相同
2、两个链表相加后,长度不一定不变
递归需要先将递归退出条件写出来,即两者都到尾部,先就简单看看我画的思路图
示例代码 1
1 | class Solution { |
其实这种递归就是化简为繁了
下面这种做法才是我觉得比较好的
示例代码 2
1 | class Solution { |
齐头并进遍历
直接两条链表一起遍历
用一个变量存储是否需要进位
这个思路其实和第二种递归的写法思路是一样的
1 | class Solution { |