LeetCode 两数相加：链表模拟加法解法

题目

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

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

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

解题思路

题目里最关键的一句是「按照逆序的方式存储」，也就是链表头存的是个位。一开始可能觉得这个设定很别扭，其实它是在帮忙——竖式加法本来就是从个位算起，逆序存储让链表的遍历方向和计算方向完全一致，从头往后走一遍就行，不需要先反转。如果改成正序存储，反而要麻烦得多，得先反转或者借助栈。

所以整体思路就是手工列竖式：两个链表同步往后走，每一步把两位数字加上进位，得到的结果个位留下作为当前位，十位作为进位带到下一轮。

有三个边界情况需要处理好，这道题的坑基本都在这里：

一是两个链表长度不等。短的那个走完之后，缺的位要按 0 参与计算，不能提前结束循环。

二是最高位产生的进位。比如 5 + 5，循环结束后还剩一个进位 1，必须在循环外单独补一个节点，漏掉这一步是最常见的错误。

三是结果链表的构造。第一个节点还没建出来的时候，没有「前一个节点」可以挂，写起来会有一堆判断。解法是先建一个哑节点顶在前面，所有真实节点都挂在它后面，最后返回它的 next。

顺带说一句，这道题不能取巧转成数字算再转回来，链表长度可以很大，远超 JS 数字的安全整数范围，转换会丢精度。要真想这么做只能用 BigInt，但那就绕开了题目本意。

题解

代码里 p1、p2 是两个输入链表的游标，p3 是结果链表的游标，carry 存进位。l3 就是上面说的哑节点，它的值 0 是占位用的，不参与结果。

var addTwoNumbers = function (l1, l2) {
  let l3 = new ListNode(0);
  let p1 = l1;
  let p2 = l2;
  let p3 = l3;
  let carry = 0;
  while (p1 || p2) {
    const _val = (p1 ? p1.val : 0) + (p2 ? p2.val : 0) + carry;
    carry = Math.floor(_val / 10);
    p3.next = new ListNode(_val % 10);
    if (p1) p1 = p1.next;
    if (p2) p2 = p2.next;
    console.log(l3);
    p3 = p3.next;
  }
  if (carry) {
    p3.next = new ListNode(carry);
  }

  return l3.next;
};

几个细节值得展开。

循环条件是 p1 || p2，只要还有一个链表没走完就继续，这样就处理了长度不等的情况。配合循环体里 (p1 ? p1.val : 0) 这种三元判断，走完的那一边自动按 0 参与，不需要为长短不一写额外分支。

进位的计算用 Math.floor(_val / 10)。这里 _val 的取值范围是 0 到 19——两个个位数最大 9 + 9，加上进位最多 1。所以进位只可能是 0 或 1，用 _val >= 10 ? 1 : 0 也一样，除法写法更通用。当前位用 _val % 10 取余数。

循环结束后那个 if (carry) 就是补最高位。例如 [5] 加 [5]，循环只跑一轮得到节点 0，进位 1 留在外面，这一步补上之后结果才是 [0, 1]，也就是十进制的 10。

返回的是 l3.next 而不是 l3，因为 l3 本身是哑节点，它的值 0 是我们自己造的，不属于计算结果。这一点写完容易忘，返回 l3 会让结果多一个前导的 0。

代码里那行 console.log(l3) 是调试时留下的，提交前应该去掉，链表长的时候它会明显拖慢运行。

关于复杂度：时间是 O(max(m, n))，两个链表各遍历一次，通常简记为 O(n)。空间上，结果链表的长度最多是较长链表加一位，所以是 O(max(m, n))。严格来说结果链表是题目要求的返回值而不是算法的额外开销，如果按「不含输出」的标准算，额外空间只有几个游标变量，是 O(1)。