Add Two Numbers 是链表题里的经典入门题，也是一道非常适合练习“哑节点 + 逐位处理 + 进位”的题目。
题目大意是：
给你两个非空链表，表示两个非负整数。数字按照逆序存储，每个节点只存储一位数字。请你将这两个数相加，并以相同形式返回一个表示和的链表。
题目示例
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：
-
l1表示数字342 -
l2表示数字465 -
342 + 465 = 807
因为题目要求结果也按逆序存储，所以返回链表 [7,0,8]
解题思路
这道题本质上就是模拟我们平时做加法的过程：
-
从两个链表的头节点开始逐位相加
-
需要考虑上一位产生的进位
carry -
当前位的结果是
sum % 10 -
新的进位是
sum / 10 -
一直处理到两个链表都遍历结束
-
如果最后还有进位，需要再补一个节点
为什么要用哑节点（dummyHead）？
在链表题中，哑节点是一个非常常见的小技巧。
它的作用是：
-
统一链表头节点的处理逻辑
-
避免单独判断“第一个节点怎么创建”
-
最后直接返回
dummyHead.next即可
这样代码会更简洁，也更不容易出错。
Java 代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(0);
ListNode p = l1, q = l2, curr = dummyHead;
int carry = 0;
while (p != null || q != null) {
int x = (p != null) ? p.val : 0;
int y = (q != null) ? q.val : 0;
int sum = carry + x + y;
carry = sum / 10;
curr.next = new ListNode(sum % 10);
curr = curr.next;
if (p != null) p = p.next;
if (q != null) q = q.next;
}
if (carry > 0) {
curr.next = new ListNode(carry);
}
return dummyHead.next;
}
}
代码拆解
1. 初始化变量
ListNode dummyHead = new ListNode(0);
ListNode p = l1, q = l2, curr = dummyHead;
int carry = 0;
这里定义了几个关键变量：
-
dummyHead：结果链表的哑节点 -
p：用于遍历链表l1 -
q：用于遍历链表l2 -
curr：始终指向结果链表的末尾 -
carry：记录进位
2. 同时遍历两个链表
while (p != null || q != null)
这里用的是“或”条件，不是“且”。
原因很简单：
-
只要有一个链表还没遍历完，就还需要继续计算
-
如果某个链表已经为空，就把该位当成
0
3. 取当前位的值
int x = (p != null) ? p.val : 0;
int y = (q != null) ? q.val : 0;
如果当前节点存在，就取它的值；如果不存在，就补 0。
这一步可以很好地处理两个链表长度不一致的情况。
4. 计算当前位和进位
int sum = carry + x + y;
carry = sum / 10;
curr.next = new ListNode(sum % 10);
这里是整道题的核心：
-
sum：当前位总和 -
sum % 10：当前位要存入新链表的值 -
sum / 10：新的进位
例如：
-
8 + 7 = 15 -
当前位存
5 -
进位变成
1
5. 指针后移
curr = curr.next;
if (p != null) p = p.next;
if (q != null) q = q.next;
每处理完一位后：
-
结果链表尾指针向后移动
-
原链表指针也继续向后遍历
6. 最后一位进位单独处理
if (carry > 0) {
curr.next = new ListNode(carry);
}
这是一个非常容易遗漏的细节。
例如：
l1 = [9,9,9]
l2 = [1]
计算过程对应：
999 + 1 = 1000
结果应该是：
[0,0,0,1]
所以如果最后还有进位，一定要再补一个节点。
示例演示
以这组数据为例：
l1 = [2,4,3]
l2 = [5,6,4]
逐位计算过程如下：
第 1 位
-
2 + 5 + 0 = 7 -
当前位放
7 -
进位
0
第 2 位
-
4 + 6 + 0 = 10 -
当前位放
0 -
进位
1
第 3 位
-
3 + 4 + 1 = 8 -
当前位放
8 -
进位
0
最终结果链表为：
[7,0,8]
复杂度分析
时间复杂度
O(max(m, n))
其中：
-
m是链表l1的长度 -
n是链表l2的长度
因为最多只遍历两个链表各一次。
空间复杂度
O(max(m, n))
原因是需要创建一个新的结果链表来保存答案。
如果只讨论额外辅助变量，那么辅助空间是 O(1)； 但按照算法题通常的口径，返回结果链表本身也算空间，因此整体空间复杂度一般写作 O(max(m, n))。
这道题的关键点
这题真正需要掌握的其实就三点：
-
用哑节点简化链表构造
-
用
carry处理进位 -
注意最后一位是否还需要补节点
只要这三点想清楚，代码实现并不复杂。
总结
Add Two Numbers 是一道非常经典的链表模拟题。
这类题做完以后，建议顺便总结一下两个常见技巧：
-
链表题里的 dummyHead
-
模拟题里的 进位 carry
这两个技巧在后面的很多题目里还会反复出现。
适合发布的结尾
如果你刚开始刷链表题，这道题很值得反复练习。
因为它同时训练了你这几项能力：
-
链表遍历
-
新链表构造
-
边界条件处理
-
进位模拟
