02_445. 两数相加 II.md

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

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

示例1： 输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[8,0,7]

示例2： 输入：l1 = [0], l2 = [0] 输出：[0]

//  利用栈先进后出得结构特点，将两条链表依次压入两个栈中，再将栈顶元素弹出、相加，得到新的节点
// 但需要处理边界，和超出进位得问题
var addTwoNumbers = function (l1, l2) {
    let stack1 = []
    let stack2 = []
    while (l1 !== null) {
        stack1.push(l1.val)
        l1 = l1.next
    }
    while (l2 !== null) {
        stack2.push(l2.val)
        l2 = l2.next
    }

    let curr = null;
    let carry = 0
    while (stack1.length != 0 || stack2.length != 0) {
        let sum = 0
        if (stack1.length != 0) {
            sum += stack1.pop()
        }
        if (stack2.length != 0) {
            sum += stack2.pop()
        }

        sum += carry // 加上进位
        const node = new ListNode((sum % 10), curr)
        carry = Math.floor(sum / 10)
        curr = node
    }

    if (carry != 0) {
        return new ListNode(1, curr)
    }
    return curr
};