两数相加

题目描述

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

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

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

示例

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

我的解题过程

第一次尝试

一开始想的就是把两个链表对应位置的数字依次相加。关键是要处理进位的问题。

我的思路是：

• 定义一个 add 变量用来标记是否有进位
• 每次相加时，把两个节点的值加上进位一起算
• 如果和大于 9，就需要进位，把个位数存到新节点里
• 继续遍历，直到两个链表都遍历完，并且没有进位了

function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
  let head = new ListNode();
  let current = head;
  let add = false;
  const judge = (isUp: boolean) => {
    const sum = (l1?.val || 0) + (l2?.val || 0) + (isUp ? 1 : 0);

    if (sum > 9) {
      add = true;
      const d = sum % 10;
      current.next = new ListNode(d);
    } else {
      current.next = new ListNode(sum);
      add = false;
    }

    l1 = l1?.next || null;
    l2 = l2?.next || null;

    current = current.next!;
  };

  while (l1 || l2 || add) {
    judge(add);
  }

  console.log("res", head.next);
  return head.next;
}

这个方法能解决问题，但代码写得有点复杂了，可以简化一下。

参考优秀题解的改进

后面看了看其他人的题解，发现可以写得更简洁一些。主要是把进位改成用数字表示（0 或 1），而不是 boolean，这样计算起来更直观。

关键的改进点：

• 用 carry 直接存进位的数字，而不是 boolean
• 用 Math.floor(sum / 10) 直接算出进位
• 用 sum % 10 直接得到当前位的值

function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
  const dummy = new ListNode(0);
  let current = dummy;
  let carry = 0;

  while (l1 || l2 || carry) {
    const val1 = l1?.val || 0;
    const val2 = l2?.val || 0;
    const sum = val1 + val2 + carry;

    carry = Math.floor(sum / 10);
    current.next = new ListNode(sum % 10);

    current = current.next;
    l1 = l1?.next || null;
    l2 = l2?.next || null;
  }

  return dummy.next;
}

这样写确实清晰很多，代码量也少了。

小结

这道题主要考察的是链表的基本操作和进位处理。几个关键点：

1. 逆序存储的好处：因为是逆序，所以从头开始遍历就是从个位开始加，正好符合加法运算的顺序
2. 进位处理：用 carry 记录进位，每次都加上进位再计算
3. 边界情况：要注意两个链表长度不一样的情况，用 || 0 来处理空节点
4. 最后的进位：循环条件要包含 carry，因为可能最后还有一个进位需要处理

这道题其实就是模拟我们手算加法的过程，理解了这个就好写了。