LeetCode系列002：两数相加

题目描述

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

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

示例

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
复制代码

题目解读

题目中给出了一种用链表的形式存储的整数，简单来说，就是将一个十进制的正整数进行了拆分，并且倒序存放到了一个链表中。也就是说链表的第一个节点对应个位、第二个节点对应十位、第三个节点对应百位……以此类推。

解题思路

这道题的解题思路和小学学过的加法问题一样，从整数的个位开始进行逐位求和，就相当于从链表的第一个节点开始向后遍历，然后对每一位进行求和运算。

这里要注意两个问题，第一个是进位问题，如果两数相加大于10，就要向前进一位，如果在最高位产生了进位，那么计算出来的链表有可能比原始链表多一位。第二个是两个链表不等长问题，需要遍历完长度最长的那个链表。

代码解读

函数会接收到两个参数，这两个参数其实是链表的第一个节点。对于链表这种数据结构来说，我们拿到了第一个节点，就相当于拿到了整个链表，所以我们的返回值也是链表的第一个节点。

节点是一个对象，它有两个属性，一个是val，代表当前节点的值，另一个是next，用来记录下一个节点。

var addTwoNumbers = function (l1, l2) {
  // head是链表的第一个节点，用于返回结果。
  // current是链表的当前节点，用于存储每一位的计算结果。
  let head = null, current = null;
  // carry用来记录进位，初始值为0
  let carry = 0;
  // l1和l2的初始值都是链表的第一个节点，每次循环都会获取下一个节点，直到节点为空。
  // 所以判断链表遍历结束的条件是节点为空，即l1 === null 或者 l2 === null
  // 只有l1和l2都遍历结束时才算结束，所以这里用了或运算
  while (l1 || l2) {
    // 分别取出两个链表当前节点的值，如果某个节点为空则赋值为0
    const n1 = l1 ? l1.val : 0;
    const n2 = l2 ? l2.val : 0;
    // 对当前位进行求和运算，注意要加上进位
    const sum = n1 + n2 + carry;
    // 如果head为空，说明是第一次循环，将当前计算结果的节点赋值给head和current
    if (!head) {
      head = current = new ListNode(sum % 10);
    } else {
      // 如果不是第一次循环，就把将当前计算结果的节点赋值给current的下一个节点
      current.next = new ListNode(sum % 10);
      // 让current指向下一个节点
      current = current.next;
    }
    // 记录一下进位，用于下一次循环的求和操作
    carry = Math.floor(sum / 10);
    // 每次计算结束后，l1和l2都要指向下一位，因为两个链表不一定等长，所以要做判空处理
    if (l1) {
      l1 = l1.next;
    }
    if (l2) {
      l2 = l2.next;
    }
  }
  // 当循环结束后，如果进位大于0，就要再最后再创建一个节点，保存进位的值
  if (carry > 0) {
    current.next = new ListNode(carry);
  }
  return head;
};
复制代码