0002. Add Two Numbers
=====================
题目信息
--------
:题号: 0002. 两数相加
:难度: Medium
:主题: 链表、模拟、进位、节点构造
:原题: `LeetCode 0002 `_
:重点: 利用逆序数位直接模拟竖式加法,并比较新建结果节点与复用输入节点的对象语义
题目重述
--------
给定两个非空单链表 ``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++ 实现
--------
.. code-block:: cpp
#include
// 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]`` 为例:
.. list-table::
:header-rows: 1
* - 列
- ``first``
- ``second``
- 旧进位
- 结果位
- 新进位
- 已构造结果
* - 个位
- 8
- 7
- 0
- 5
- 1
- ``5``
* - 十位
- 9
- 0
- 1
- 0
- 1
- ``5 -> 0``
* - 百位
- 9
- 0
- 1
- 0
- 1
- ``5 -> 0 -> 0``
* - 千位
- 0
- 0
- 1
- 1
- 0
- ``5 -> 0 -> 0 -> 1``
前三轮消费输入节点。第四轮开始时两个输入指针都为空,进位仍为 ``1``,因此算法继续创建最后一个节点。
节点复用
~~~~~~~~
逐位加法已经把时间降到线性,还可以从节点分配角度继续优化。结果最多比较长的输入多一个节点,因此可以先找出较长链表,把每一列的结果直接写回它的现有节点;只有最终仍有进位时才需要新建一个节点。
``reuseLongerList`` 先扫描两条链表获得长度,并通过交换局部指针保证 ``l1`` 指向较长链表。之后的加法状态与主解法相同,区别只是把 ``total % 10`` 写入 ``l1->val``,而不是创建新节点。
这种方法减少了节点分配,却会修改其中一条输入链表,返回结果还与输入节点共享身份。它并不是无条件更好的实现;当接口要求保留输入,或调用者仍需使用原链表时,新建结果链表更安全。
代码演进
~~~~~~~~
把链表还原成普通整数需要保存最多 ``100`` 位的完整数值,固定宽度整数无法承担这一状态。逐位模拟将状态缩减为当前两个数位和一个进位,使代码只需同步推进两个链表指针。
``buildNewList`` 使用哑节点统一首节点与后续节点的追加过程,并把最终进位并入循环条件。代码不需要预先判断链表长度,也不需要为第一位和最后进位分别编写特殊分支。
``reuseLongerList`` 保留相同的逐位状态,改变的是结果存储方式:新节点创建被改成覆盖较长输入节点。为保证现有节点足够,它增加了长度扫描和输入修改,换取绝大多数情况下零节点分配。
主解法选择 ``buildNewList``。这道题的核心优化是避免构造完整整数,而不是强行减少结果节点;保持输入不变比节省节点分配具有更清晰的通用语义。
复杂度分析
~~~~~~~~~~
.. list-table::
:header-rows: 1
* - 方法
- 时间复杂度
- 辅助空间
- 节点分配
- 输入状态
* - 新建结果链表
- ``O(max(m, n))``
- ``O(1)``
- 每个结果位一个节点
- 保持不变
* - 复用较长链表
- ``O(m + n)``
- ``O(1)``
- 至多一个节点
- 较长链表被修改
设两条输入链表长度分别为 ``m`` 和 ``n``。主解法每轮至少消费一个输入节点,输入结束后最多再处理一次最终进位,因此时间复杂度为 ``O(max(m, n))``。返回链表自身占用 ``O(max(m, n))`` 结果空间;除返回节点外,只维护常数个指针和整数状态。
复用方案需要先扫描两条链表求长度,再覆盖较长链表,访问节点总量为 ``O(m + n)``;它只使用常数辅助状态,但返回结果复用了输入节点。
边界处理
~~~~~~~~
* 输入表示数字 ``0`` 时,单节点 ``[0]`` 会正常参与加法,不会生成多余高位零;
* 一条链表先结束时,缺失数位按 ``0`` 处理,另一条链表继续向高位推进;
* 两条链表都结束后仍有进位时,循环额外创建一个最高位节点;
* 两条链表都非空,因此复用方案中的 ``previous`` 在追加最终进位前一定已经指向有效节点。