LeetCode 02 两数相加

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例1:

l1: 2 —–> 4 —–> 3

l2: 5 —–> 6 —–> 4

结果: 7 —–> 0 —–> 8

示例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]

提示:

每个链表中的节点数在范围 [1, 100] 内

0 <= Node.val <= 9

题目数据保证列表表示的数字不含前导零

刚拿到这题，发现链表表示的数字是从低位到高位的，随即就觉得如果将链表中的数值全部取出放置到数组中，然后将数组反转拼接就是对应的数字，将两个数字直接相加，就省去了计算进位等等之类的麻烦，在最后将数字切割，变成新的链表就完成了。写完一跑超时了QAQ。看了下，发现测试用例里面有个大几十位的链表，石化。

回头思考一下，这样做循环了l1.length + l2.length + sum.length次，但是实际上，这些循环都可以放到一起做，既然链表是从低位到高位，那么计算的时候就可以直接得出从低位到高位的结果，只是需要额外注意下有进位的问题。如果两个链表的长度不一致，那么就相当于在短的链表的高位上进行补0。这样总共相当于只循环了l1和l2中较长的那个链表的length次。

var addTwoNumbers = function(l1, l2) {
    let acc = 0
    function innerCalc(a1, a2) {
        a1 = a1 || new ListNode(0, null)   // 这里相当于在没有终止循环前，在数值的高位进行补0
        a2 = a2 || new ListNode(0, null)
        const sum = a1.val + a2.val + acc  // 按位求和
        const curr = sum % 10              // 求模 得到这一位上的值
        acc = Math.floor(sum / 10)         // 获取这一位上进行的求和有没有进位

        //退出循环的条件 a1和a2链表的下一级不存在，且此时没有进位，就会退出循环
        // 如果[0,0,5] + [0,0,5] 实际上除了链表加完之外，还需要为进位增加一次循环，不然就变成了 [0,0,0] 而不是 [0,0,0,1]
        if (a1.next !== null || a2.next !== null || acc !== 0) {   
            return new ListNode(curr, innerCalc(a1.next, a2.next)) //这里使用递归完成next的节点的计算
        }
        return new ListNode(curr, null) //如果不满足条件，那么next为null
    }
    return innerCalc(l1, l2)
};

状态演示

示例1:

[2, 4, 3]
[5, 6, 4]

2 + 5 + 0 = 7 , acc = 0 , 节点值7, l1还有next, l2 还有next, 继续递归
4 + 6 + 0 = 10, acc = 1 , 节点值0, l1还有next, l2 还有next, 继续递归
3 + 4 + 1 = 8, acc = 0, 节点值8, l1没有next, l2没有next, acc == 0 停止递归

最后结果 [7, 0, 8]

示例2:

[9,9,9,9,9,9,9]
[9,9,9,9]

9 + 9 + 0 = 18, acc = 1, 节点值8, l1还有next, l2还有next, 继续递归
9 + 9 + 1 = 19, acc = 1, 节点值9, l1还有next, l2还有next, 继续递归
9 + 9 + 1 = 19, acc = 1, 节点值9, l1还有next, l2还有next, 继续递归
9 + 9 + 1 = 19, acc = 1, 节点值9, l1还有next, l2没有next, 进行补0, 继续递归
9 + 0 + 1 = 10, acc = 1, 节点值0, l1还有next, l2没有next, 进行补0, 继续递归
9 + 0 + 1 = 10, acc = 1, 节点值0, l1还有next, l2没有next, 进行补0, 继续递归
9 + 0 + 1 = 10, acc = 1, 节点值0, l1没有next, l2没有next, acc !== 0, l1和l2补0, 继续递归
0 + 0 + 1 = 1, acc = 0, 节点值1, l1没有next, l2没有next, acc == 0, 停止递归

最后结果 [8, 9, 9, 9, 0, 0, 0, 1]