leetcode：两数相加II

描述：

题解：

思路一：反转链表

在前面做过两数相加和反转链表的题目。这道题最容易想到的解决思路就是把前面两个题结合起来。

ES6

export function addTwoNumbers(l1, l2) {
  l1 = reverseList(l1);
  l2 = reverseList(l2);
  let p = l1,
    q = l2,
    carry = 0; //进位
  const res = new ListNode(null);
  let cur = res;
  while (p || q || carry === 1) {
    const sum = (p ? p.val : 0) + (q ? q.val : 0) + carry;
    carry = (sum / 10) | 0;
    cur.next = new ListNode(sum % 10);
    cur = cur.next;
    if (p) {
      p = p.next;
    }
    if (q) {
      q = q.next;
    }
  }
  return reverseList(res.next);
}

function reverseList(linkedList) {
  //定义三个指针：前一个节点，当前节点，下一个节点
  let prev = null
  let curr = linkedList
  let nextTemp
  while (curr != null) {
    //存储下一个节点
    nextTemp = curr.next
    //把当前节点的next设置为prev
    curr.next = prev
    //当前节点变成上一个节点
    prev = curr
    //下一个节点变成当前节点
    curr = nextTemp
  }
  return prev
}

思路二：借助栈

题目的进阶要求是不能对链表的节点进行翻转，那么我们应该如何处理。对于逆序的操作，我们首先想到的就是栈。因为栈后进先出的特点，我们可以先把所有的数字压入栈中，再依次取出相加。

我们可以画图分析一下。首先，两个链表都进栈：

接下来，3 和 4 分别出栈。我们把它们相加得到 7。

接下来，4 和 6 分别出栈。我们把它们相加得到 0，并产生一个进位。

接下来，一直重复这样的动作就可以了。这里需要注意几点：

1. 相加的过程中可能会产生进位
2. 栈为空时，也就是最后一次相加时，也可能会产生一个进位
3. 我们可以使用头插法来构建最终返回的链表

ES6

export function addTwoNumbers(l1, l2) {
  //用数组的push和pop模拟栈
  const stack1 = [];
  const stack2 = [];
  while (l1 != null) {
    stack1.push(l1.val);
    l1 = l1.next;
  }

  while (l2 != null) {
    stack2.push(l2.val);
    l2 = l2.next;
  }

  const head = new ListNode(null);
  let carry = 0;
  //头插法构建链表
  while (stack1.length || stack2.length || carry === 1) {
    const sum =
      (stack1.length ? stack1.pop() : 0) +
      (stack2.length ? stack2.pop() : 0) +
      carry;
    carry = (sum / 10) | 0;

    const node = new ListNode(sum % 10);
    node.next = head.next;
    head.next = node;
  }
  return head.next;
}