Hot 100 --- 两数相加

本文概览：本文以LeetCode经典题目"两数相加"为例，从题目特点入手，重点讲解链表倒序存储带来的便利，以及如何通过 sum 和 carry 两个变量优雅处理进位问题

一、题目

二、题目分析

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

目标：将两个数相加，并以相同形式返回一个表示和的链表

核心特点：倒序存储

题目中链表是倒序存储的，比如数字 342 表示为：

2 → 4 → 3

这其实非常方便，因为加法本来就是从最低位开始算的。倒序链表的头节点刚好就是最低位，所以我们不需要反转链表，直接从头开始逐位相加即可

核心难点：进位处理

这道题思路不难，真正容易写乱的是进位：当前两位相加如果大于等于 10，就需要给下一位进 1。链表是动态创建的，不能提前给 temp.next.next 加 1，所以需要用变量来保存进位

思路概览

Java实现代码如下

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode temp = new ListNode(-1);
ListNode head = temp;
// 初始化
int carry = 0;
while (l1 != null || l2 != null || carry != 0) {
int sum = carry;
if (l1 != null) {
sum += l1.val;
l1 = l1.next;
}
if (l2 != null) {
sum += l2.val;
l2 = l2.next;
}
// 处理进位
carry = sum / 10;
sum %= 10;
// 创建新节点
temp.next = new ListNode(sum);
temp = temp.next;
}
return head.next;
}

思路简要说明

三、思路详解

暴力思路为什么不适合

如果不考虑链表特性，可能会想到：先把两个链表还原成数字，相加后再拆成链表

但这个思路有两个问题：

• 数字可能非常大：链表长度可能很长，转成 int 或 long 都可能溢出
• 没有必要还原整个数字：加法本来就是逐位进行的，我们完全可以模拟竖式加法

所以正确的方向不是把链表转成数字，而是直接在链表上模拟加法

竖式加法的过程

我们平时做加法时，是从低位开始：

342
+ 465
—–
807

计算顺序是：

而题目中链表是倒序存储的：

l1: 2 → 4 → 3
l2: 5 → 6 → 4

这刚好对应从个位到百位的顺序，因此我们只需要两个指针分别遍历 l1 和 l2，每轮把当前节点值相加即可

为什么需要虚拟头节点

结果链表是动态创建的。如果没有虚拟头节点，就需要额外判断当前是否是第一个节点：

• 如果是第一个节点，要初始化结果链表头节点
• 如果不是第一个节点，才可以执行 temp.next = new ListNode(…)

这样代码会多出很多特殊判断

所以我们先创建一个虚拟头节点：

ListNode temp = new ListNode(-1);
ListNode head = temp;

其中：

• head 永远指向虚拟头节点，用于最后返回 head.next
• temp 负责移动，始终指向结果链表的最后一个节点

这样每次创建新节点时都可以统一写：

temp.next = new ListNode(sum);
temp = temp.next;

最后返回 head.next，跳过虚拟头节点即可

进位为什么不能直接加到下一个节点

这道题最容易写乱的地方就是进位

假设当前两位相加大于等于 10，需要给下一位加 1。一个直觉做法可能是：直接把这个 1 加到结果链表的下一个节点上

但问题是：结果链表的下一个节点此时还没有创建

比如：

l1: 9
l2: 9

当前位相加：9 + 9 = 18

如果想把进位直接加到下一位，直觉上可能会想这样：

当前已经创建的结果链表：

head(-1) → 8
↑
temp

想要把进位1加到下一位：

head(-1) → 8 → ?
↑
这里的节点还不存在

也就是说，此时结果链表里只有当前位节点 8，下一位节点还没有创建，根本不存在可以加 1 的位置。如果强行去想 temp.next.next，一定会出问题，因为 temp.next 可能都是 null，更不用说 temp.next.next

而最终正确的结果应该是：

head(-1) → 8 → 1

返回 head.next：8 → 1

所以问题的本质是：进位属于下一轮计算，但下一轮的节点现在还没有创建

这就是为什么不能直接操作链表节点来处理进位，而是要用一个变量 carry 暂时保存下来。等下一轮循环开始时，再通过 sum = carry 把这个进位自然加进去

sum 和 carry 的配合

解决进位问题的关键是两个变量：

• sum：当前这一位的总和
• carry：当前这一位产生的进位，留给下一位使用

每一轮循环开始时：

int sum = carry;

这一步非常关键。上一轮留下来的进位，会在下一轮一开始自然加入当前位计算

然后加上两个链表当前节点的值：

if (l1 != null) {
sum += l1.val;
l1 = l1.next;
}
if (l2 != null) {
sum += l2.val;
l2 = l2.next;
}

接着处理当前位和进位：

carry = sum / 10;
sum %= 10;

含义是：

• sum % 10：当前节点真正应该存的值
• sum / 10：需要进到下一位的值

例如 sum = 18：

• 当前位存 18 % 10 = 8
• 下一位进 18 / 10 = 1

为什么循环条件要包含 carry != 0

循环条件是：

while (l1 != null || l2 != null || carry != 0)

这三个条件分别表示：

• l1 != null：第一个链表还有位数没加完
• l2 != null：第二个链表还有位数没加完
• carry != 0：链表都加完了，但还有最后一个进位没处理

最后一个条件特别重要

例如：

l1: 9
l2: 9

第一轮：

sum = 0 + 9 + 9 = 18
当前位 = 8
carry = 1

此时 l1 == null，l2 == null，但 carry == 1，所以还需要继续循环一轮：

sum = carry = 1
当前位 = 1
carry = 0

最终结果才是：

8 → 1

如果循环条件没有 carry != 0，结果就会错误地变成只有 8

举例说明

以 l1 = 2 → 4 → 3，l2 = 5 → 6 → 4 为例

最终结果为 7 → 0 → 8，表示数字 807

再看一个进位到最后的例子：l1 = 9，l2 = 9

最终结果为 8 → 1

• 时间复杂度：O(max(m, n))，m 和 n 分别为两个链表长度
• 空间复杂度：O(max(m, n))，结果链表需要存储最终答案；除结果链表外只用了常数变量