如何用链表表示两个数并相加？

简化版

两数相加链表题通常按位从低位到高位相加，用一个 carry 保存进位，用 dummy 构建结果链表。每轮取两个链表当前值和进位相加，当前位是 sum % 10，新进位是 sum / 10。

详细版

例如 342 + 465 = 807，链表逆序表示为：

2 -> 4 -> 3
5 -> 6 -> 4
结果:
7 -> 0 -> 8

因为低位在链表头部，所以可以从头开始直接相加。循环条件要覆盖两个链表长度不同和最后 carry 不为 0 的情况：while (l1 != null || l2 != null || carry != 0)。

完整版教学

一、逆序链表让加法从低位开始

小学加法从个位开始，因为个位产生的进位会影响十位。链表如果低位在头部，就非常适合顺序遍历。

342 represented as 2 -> 4 -> 3
465 represented as 5 -> 6 -> 4

第一轮算个位 2 + 5 = 7，第二轮算十位 4 + 6 = 10，第三轮算百位加进位。

记忆钩子：链表头是低位，就像从个位往高位竖式相加。

二、每一位只需要 sum、digit、carry

核心公式：

sum = x + y + carry
digit = sum % 10
carry = sum / 10

如果 sum = 17，当前位写 7，进位 1。如果 sum = 5，当前位写 5，进位 0。

代码：

int sum = x + y + carry;
tail.next = new ListNode(sum % 10);
carry = sum / 10;
tail = tail.next;

这就是整题的数学核心。

三、dummy 用来构建结果链表

结果链表长度未知，可能比两个输入都长 1 位，比如 999 + 1 = 1000。用 dummy 和 tail 可以稳定尾插。

ListNode dummy = new ListNode(0);
ListNode tail = dummy;

每算出一位，就创建一个新节点接到 tail 后面。最后返回 dummy.next。

不用 dummy 也能写，但第一位结果要特殊处理，代码更容易乱。

四、长度不同按 0 补齐

如果一个链表走完了，当前位就当 0。

99 + 1

9 -> 9
1

round1: 9 + 1 + 0 = 10 -> digit 0 carry 1
round2: 9 + 0 + 1 = 10 -> digit 0 carry 1
round3: 0 + 0 + 1 = 1  -> digit 1 carry 0

结果是：

0 -> 0 -> 1

所以循环条件必须包含 carry != 0。

五、完整代码结构

ListNode addTwoNumbers(ListNode l1, ListNode l2) {
  ListNode dummy = new ListNode(0);
  ListNode tail = dummy;
  int carry = 0;

  while (l1 != null || l2 != null || carry != 0) {
    int x = (l1 == null) ? 0 : l1.val;
    int y = (l2 == null) ? 0 : l2.val;
    int sum = x + y + carry;

    tail.next = new ListNode(sum % 10);
    tail = tail.next;
    carry = sum / 10;

    if (l1 != null) l1 = l1.next;
    if (l2 != null) l2 = l2.next;
  }
  return dummy.next;
}

时间 O(max(m,n))，额外空间 O(max(m,n)) 用于结果链表。除了结果本身，只用了常数变量。

六、正序链表版本怎么处理

如果数字正序表示：

342 as 3 -> 4 -> 2

就不能直接从头相加，因为进位从尾部向前传。常见做法有 2 种：

方法	思路	代价
反转链表	反转后按逆序版本处理	会改链表或需恢复
栈	把节点值压栈，从尾部弹出	额外 O(n) 空间

面试中要先问清楚链表表示顺序。低位在头和高位在头，解法不一样。

七、常见误区与追问

误区：两个链表长度一定相同。 长度不同的缺失位要按 0 处理。
误区：循环到两个链表都空就结束。 最后 carry 可能还要生成新节点。
误区：可以直接转成整数相加。 大数可能溢出，题目考链表逐位运算。
追问：为什么用 dummy？ 结果链表头未知，用 dummy 统一尾插和返回。
追问：正序表示怎么办？ 可以反转链表或用栈从低位开始处理。
追问：复杂度是多少？ 时间 O(max(m,n))，结果链表空间 O(max(m,n))。

八、加强记忆

两数相加链表题记成“逐位加、进位走、dummy 接”。逆序链表天然从低位开始，当前位用 sum % 10，进位用 sum / 10，循环条件必须带上 carry != 0。如果输入是正序，就先考虑反转或栈，不能硬从头加。

简化版

详细版