题目
给出两个非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照逆序的方式存储的,并且它们的每个节点只能存储 一位 数字。
如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例:
1
2
3 输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/add-two-numbers
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
两数相加需要进位,是一个很明显的动作,进位条件为i+j>=10
,i
和j
分别为两链表对应的节点表示的位,表头代表低位。
进位:当前相加的位对10取余,下一位加一,链式进位直到不需要进位。如果当前最高位需要进位,那么创造新的节点并赋值为1。
需要注意的是,最低位永远是个位,那么从表头开始遍历,每个节点对应的位在两个链表之间是匹配的。
但是如果每次进位都要顺序访问一遍链表会使时间复杂度为$O(N^2)$,因此为了只遍历一次,我们把进位操作延迟。
考虑遍历l1
,期间访问l2
对应节点,两链表非空。
l1
未到达结尾l2
非空,相加并进位l2
为空,进位
l1
到达结尾后,l2
并未到达结尾- 拼接
写得太复杂了,且逻辑不清晰
1 | /** |
- 时间复杂度$O(max(len_{l1},len_{l2}))$;
- 空间复杂度$O(1)$。