2021-03-08 | 445. 两数相加 II

╰半橙微兮° 2022-11-12 11:51 226阅读 0赞

### 1. 题目描述 ###

给你两个 **非空** 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。  
你可以假设除了数字 0 之外，这两个数字都不会以零开头。

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

**示例：**

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

### 2. 解题思路 ###

对于这道题目，我们可以先用两个栈分别将两个链表的元素push存储起来，然后再从个位开始将两个数组对应的元素相加即可，详细步骤如下：

*  初始化stack1和stack2两个栈，并遍历两个链表，将链表元素存储起来；
 *  初始化一个空的节点dummyHead来储存新的链表的值；
 *  遍历两个栈，从栈的最后分别取元素，进行相加，超过10的部分进行进位，小于10的部分就作为当前点的和，放在结果链表dummyHead中
 *  当两个栈都为空的时候，结束遍历
 *  最后判断一下，如果最后一次相加之后还有进位值，记得加在链表上

**复杂度分析：**

*  时间复杂度：O(max(m, n))，其中 m 与 n 分别为两个链表的长度，我们需要遍历每个链表。
 *  空间复杂度：O(m + n)，其中 m 与 n 分别为两个链表的长度，这是把链表内容放入栈中所用的空间。

### 3. 代码实现 ###

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */
    /** * @param {ListNode} l1 * @param {ListNode} l2 * @return {ListNode} */
    var addTwoNumbers = function(l1, l2) { 
        let stack1 = [], stack2 = [];
    
        while(l1){ 
            stack1.push(l1)
            l1 = l1.next
        }
        while(l2){ 
            stack2.push(l2)
            l2 = l2.next
        }
    
        let dummyHead = { next: null}
        let carry = 0
    
        while(stack1.length || stack2.length){ 
            let p1 = stack1.pop()
            let p2 = stack2.pop()
    
            let x = p1 ? p1.val : 0
            let y = p2 ? p2.val : 0
    
            let sum = x + y + carry
            let m = sum % 10   //个位
            let n = Math.floor(sum / 10)
            dummyHead.next = {  val: m, next: dummyHead.next}
            carry = n
        }
    
        if(carry){ 
            dummyHead.next =  {  val: carry , next: dummyHead.next };
        }
        return dummyHead.next
    };

### 4. 提交结果 ###

![在这里插入图片描述][20210323225932771.png]

[20210323225932771.png]: /images/20221022/d09ffea276b14bbf8e35e7d83d2e1acc.png?