[leetcode]No. 445 两数相加 II

[liangbus]

No. 445 两数相加 II

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

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

 

进阶：

如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。

示例：

输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 8 -> 0 -> 7

这题看起来真的是挺简单，但是做起来又没那么容易，我刚开始就是总感觉还差一丢丢就解出来了，然后就越搞越复杂

开始我是先选择忽略进阶的提示，选择用链表翻转来搞（又正好可以重温一下翻转链表的算法了~）翻过来后，然后就开始逐位遍历相加，将每位的结果存到新的链表中，然后又将链表反转，看起来是行得通的，但无奈就是绕太多了，而且计算量一点也不小，于是看了题解。

栈

没错，利用栈的特性 —— 后进先出（其实栈可以帮我们解决很多倒序相关的问题，嗯没错，重要的还是思想的拓展 -3-），将链表的值保存在栈中，然后对栈的值进行相加，因为最终也是要输出一个链表，所以不能将其直接转化为数字相加，仍需要一位位去相加，这里有点像普通的两字符串数字相加了，只不过要稍加注意的是，遍历的同时，需要通过头部插入法去创建链表，意思就是将前一个变量中，当前新建的，指向前一个，然后当前的变为前一个，进行下一轮循环，如此类推

var addTwoNumbers = function(l1, l2) {
    const stack1 = []
    const stack2 = []
    let curNode = l1
    while(curNode) {
        stack1.push(curNode.val)
        curNode = curNode.next
    }
    curNode = l2
    while(curNode) {
        stack2.push(curNode.val)
        curNode = curNode.next
    }
    let maxLen = Math.max(stack1.length, stack2.length)
    if(stack1.length < maxLen) {
        stack1.unshift(...(new Array(maxLen - stack1.length).fill(0)))
    } else {
        stack2.unshift(...(new Array(maxLen - stack2.length).fill(0)))
    }
    curNode = null
    let i = maxLen - 1
    let forward = false
    let link = null
    let next = null
    while(i >= 0) {
        let tmpSum = stack1[i] + stack2[i] + (forward ? 1 : 0)
        forward = tmpSum >= 10
        link = new ListNode(forward ? tmpSum - 10 : tmpSum)
        link.next = next
        next = link
        i--
    }
    //进1
    if(forward) {
        link = new ListNode(1)
        link.next = next
    }
    return link
};