1. 题目描述

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

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

示例：

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

2. 解题思路

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

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

复杂度分析：

  • 时间复杂度：O(max(m, n))，其中 m 与 n 分别为两个链表的长度，我们需要遍历每个链表。

  • 空间复杂度：O(m + n)，其中 m 与 n 分别为两个链表的长度，这是把链表内容放入栈中所用的空间。

    3. 代码实现

    1. /**
    2. * Definition for singly-linked list.
    3. * function ListNode(val) {
    4. *     this.val = val;
    5. *     this.next = null;
    6. * }
    7. */
    8. /**
    9. * @param {ListNode} l1
    10. * @param {ListNode} l2
    11. * @return {ListNode}
    12. */
    13. var addTwoNumbers = function(l1, l2) {
    14.   let stack1 = [], stack2 = [];
    16.   while(l1){
    17.       stack1.push(l1)
    18.       l1 = l1.next
    19.   }
    20.   while(l2){
    21.       stack2.push(l2)
    22.       l2 = l2.next
    23.   }
    25.   let dummyHead = {next: null}
    26.   let carry = 0
    28.   while(stack1.length || stack2.length){
    29.       let p1 = stack1.pop()
    30.       let p2 = stack2.pop()
    32.       let x = p1 ? p1.val : 0
    33.       let y = p2 ? p2.val : 0
    35.       let sum = x + y + carry
    36.       let m = sum % 10   //个位
    37.       let n = Math.floor(sum / 10)
    38.       dummyHead.next = { val: m, next: dummyHead.next}
    39.       carry = n
    40.   }
    42.   if(carry){
    43.       dummyHead.next =  { val: carry , next: dummyHead.next };
    44.   }
    45.   return dummyHead.next
    46. };

    4. 提交结果

    image.png