算法连载之求解两数相加 Add Two Numbers

求解两数相加

两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。

如果，将这两个数相加起来，则会返回一个新的链表来表示它们的和。

可以假设除了数字0之外，这两个数都不会以0开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)

输出：7 -> 0 -> 8

原因：342 + 465 = 807

实现

同时遍历l1和l2两个链表，将两个节点值相加作为返回链表的新节点。有两种特殊情况：

1、其中一个链表已经全部遍历完成，则只关注两一个链表的节点作为加数即可，因为另一个链表已遍历完成，所以可以看作加数为0。

2、两个链表节点之和若存在进位的情况，则先记录，下一次遍历时同加数相加。如果两个链表均遍历完成，仍然有进位，则新建一个节点存储进位。

若l1和l2两个链表长度分别是n和m，时间复杂度是O(max(n,m))；由于新增返回链表，长度至少是两个链表的最大长度，所以空间复杂度是O(max(n,m))。

拓展问题

各自的位数是按照正序的方式存储。

示例：

输入：(3 -> 4 -> 2) + (4 -> 6 -> 5)

输出：8 -> 0 -> 7

原因：342 + 465 = 807

可以借助栈的后进先出特性来解决。首先将两个链表分别压入两个栈中，相加的主算法与逆序的方式相似。区别是：由于返回的链表也是正序的，低位运算的节点要作为后继节点，始终向链表头添加。

时间复杂度仍然是O(max(n,m))；新增返回链表和两个辅助栈，空间复杂度是O(max(n,m))。