0002. Add Two Numbers¶
题目信息¶
- 题号:
两数相加
- 难度:
Medium
- 主题:
链表、模拟、进位、节点构造
- 原题:
- 重点:
利用逆序数位直接模拟竖式加法,并比较新建结果节点与复用输入节点的对象语义
题目重述¶
给定两个非空单链表 l1 和 l2,它们分别表示两个非负整数。每个节点保存一位十进制数字,链表头节点是个位,沿 next 方向依次表示十位、百位和更高位。
需要计算两个整数之和,并返回一个采用相同逆序数位表示的新链表。输入链表长度都在 [1, 100] 内,节点值位于 [0, 9];除数字 0 本身外,输入数字没有多余的最高位零。
自建示例¶
等长且无最终进位:
l1 = [2, 4, 3]、l2 = [5, 6, 4],表示342 + 465,返回[7, 0, 8];长度不同且连续进位:
l1 = [8, 9, 9]、l2 = [7],表示998 + 7,返回[5, 0, 0, 1];单独保留剩余高位:
l1 = [3, 4]、l2 = [6, 5, 9],表示43 + 956,返回[9, 9, 9];数字零:
l1 = [0]、l2 = [0],返回[0],不会额外生成高位零节点。
C++ 实现¶
#include <utility>
// ListNode 由 LeetCode 平台提供。
class Solution {
private:
ListNode* buildNewList(ListNode* l1, ListNode* l2) {
ListNode dummy(0);
ListNode* tail = &dummy;
int carry = 0;
while (l1 != nullptr || l2 != nullptr || carry != 0) {
const int first = l1 == nullptr ? 0 : l1->val;
const int second = l2 == nullptr ? 0 : l2->val;
const int total = first + second + carry;
tail->next = new ListNode(total % 10);
tail = tail->next;
carry = total / 10;
if (l1 != nullptr) {
l1 = l1->next;
}
if (l2 != nullptr) {
l2 = l2->next;
}
}
return dummy.next;
}
int length(ListNode* node) {
int result = 0;
while (node != nullptr) {
++result;
node = node->next;
}
return result;
}
ListNode* reuseLongerList(ListNode* l1, ListNode* l2) {
if (length(l1) < length(l2)) {
std::swap(l1, l2);
}
ListNode* const head = l1;
ListNode* previous = nullptr;
int carry = 0;
while (l1 != nullptr) {
const int second = l2 == nullptr ? 0 : l2->val;
const int total = l1->val + second + carry;
l1->val = total % 10;
carry = total / 10;
previous = l1;
l1 = l1->next;
if (l2 != nullptr) {
l2 = l2->next;
}
}
if (carry != 0) {
previous->next = new ListNode(carry);
}
return head;
}
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
return buildNewList(l1, l2);
}
};
题解¶
整数还原的限制¶
最直观的想法是先把两条链表还原成普通整数,完成一次整数加法,再把结果拆回链表。这种方法把链表问题转成了熟悉的数值运算,但每条链表最多包含 100 位十进制数字,远超常见固定宽度整数能够表示的范围。
真正需要的不是保存完整整数,而是复现竖式加法在每一列进行的局部计算。这样无论数字有多少位,每轮都只处理两个一位数和一个进位。
逆序数位¶
十进制竖式加法必须从最低位开始,因为当前列产生的进位会影响下一列。题目恰好把个位放在链表头部,因此链表的自然遍历顺序就是 个位 → 十位 → 百位 → 更高位,不需要反转链表或借助栈寻找最低位。
处理当前列时,若两条链表的当前数字分别为 first 和 second,前一列进位为 carry,则当前总和为 total = first + second + carry。写入结果链表的数字是 total % 10,传给下一列的进位是 total / 10。
节点值最大为 9,旧进位最大为 1,所以 total 最大为 19,新进位只可能是 0 或 1。已经处理过的全部低位对后续计算的影响,可以压缩成一个 carry。
长度差异¶
两条链表长度不同时,较短链表会先结束。竖式加法中缺失的高位等价于数字 0,所以当前指针为空时直接令对应数位为 0,同一个循环就能覆盖“两侧都有节点”和“只剩一侧节点”两种情况。
循环条件还必须包含 carry != 0。当两条输入链表都结束后,最高列仍可能留下进位;继续一轮才能把它写成新的最高位节点。若只检查两个输入指针,998 + 7 会错误地丢失结果中的千位 1。
哑节点构造¶
结果链表开始时没有真实头节点。若直接维护头指针,创建第一个节点时需要特殊处理,后续节点则采用另一套追加逻辑。
buildNewList 使用栈上的哑节点 dummy 作为固定前驱,tail 始终指向当前结果尾部。每一轮都执行相同的两步:把新节点接到 tail->next,再让 tail 移到新节点。最终返回 dummy.next,哑节点本身不属于结果。
这种实现为每个结果数位创建独立节点,不修改两个输入链表,也不与输入共享节点。输入状态和返回链表的所有权最清晰,因此公开入口选择这一方案。
状态演化¶
以 l1 = [8, 9, 9]、l2 = [7] 为例:
列 |
|
|
旧进位 |
结果位 |
新进位 |
已构造结果 |
|---|---|---|---|---|---|---|
个位 |
8 |
7 |
0 |
5 |
1 |
|
十位 |
9 |
0 |
1 |
0 |
1 |
|
百位 |
9 |
0 |
1 |
0 |
1 |
|
千位 |
0 |
0 |
1 |
1 |
0 |
|
前三轮消费输入节点。第四轮开始时两个输入指针都为空,进位仍为 1,因此算法继续创建最后一个节点。
节点复用¶
逐位加法已经把时间降到线性,还可以从节点分配角度继续优化。结果最多比较长的输入多一个节点,因此可以先找出较长链表,把每一列的结果直接写回它的现有节点;只有最终仍有进位时才需要新建一个节点。
reuseLongerList 先扫描两条链表获得长度,并通过交换局部指针保证 l1 指向较长链表。之后的加法状态与主解法相同,区别只是把 total % 10 写入 l1->val,而不是创建新节点。
这种方法减少了节点分配,却会修改其中一条输入链表,返回结果还与输入节点共享身份。它并不是无条件更好的实现;当接口要求保留输入,或调用者仍需使用原链表时,新建结果链表更安全。
代码演进¶
把链表还原成普通整数需要保存最多 100 位的完整数值,固定宽度整数无法承担这一状态。逐位模拟将状态缩减为当前两个数位和一个进位,使代码只需同步推进两个链表指针。
buildNewList 使用哑节点统一首节点与后续节点的追加过程,并把最终进位并入循环条件。代码不需要预先判断链表长度,也不需要为第一位和最后进位分别编写特殊分支。
reuseLongerList 保留相同的逐位状态,改变的是结果存储方式:新节点创建被改成覆盖较长输入节点。为保证现有节点足够,它增加了长度扫描和输入修改,换取绝大多数情况下零节点分配。
主解法选择 buildNewList。这道题的核心优化是避免构造完整整数,而不是强行减少结果节点;保持输入不变比节省节点分配具有更清晰的通用语义。
复杂度分析¶
方法 |
时间复杂度 |
辅助空间 |
节点分配 |
输入状态 |
|---|---|---|---|---|
新建结果链表 |
|
|
每个结果位一个节点 |
保持不变 |
复用较长链表 |
|
|
至多一个节点 |
较长链表被修改 |
设两条输入链表长度分别为 m 和 n。主解法每轮至少消费一个输入节点,输入结束后最多再处理一次最终进位,因此时间复杂度为 O(max(m, n))。返回链表自身占用 O(max(m, n)) 结果空间;除返回节点外,只维护常数个指针和整数状态。
复用方案需要先扫描两条链表求长度,再覆盖较长链表,访问节点总量为 O(m + n);它只使用常数辅助状态,但返回结果复用了输入节点。
边界处理¶
输入表示数字
0时,单节点[0]会正常参与加法,不会生成多余高位零;一条链表先结束时,缺失数位按
0处理,另一条链表继续向高位推进;两条链表都结束后仍有进位时,循环额外创建一个最高位节点;
两条链表都非空,因此复用方案中的
previous在追加最终进位前一定已经指向有效节点。