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`` 在追加最终进位前一定已经指向有效节点。