0002. Add Two Numbers

题目信息

题号:
  1. 两数相加

难度:

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++ 实现

#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] 为例:

列

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。这道题的核心优化是避免构造完整整数,而不是强行减少结果节点;保持输入不变比节省节点分配具有更清晰的通用语义。

复杂度分析

方法

时间复杂度

辅助空间

节点分配

输入状态

新建结果链表

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