力扣-2.两数相加（Add Two Numbers）

最后编辑于2025-5-20

2. 两数相加（Add Two Numbers）

中等

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

示例图片
输入： l1 = [2,4,3], l2 = [5,6,4]
输出： [7,0,8]
解释： 342 + 465 = 807

示例 2：

输入： l1 = [0], l2 = [0]
输出： [0]

示例 3：

输入： l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出： [8,9,9,9,0,0,0,1]
解释： 9999999 + 9999 = 10009998

提示：

  • 每个链表中的节点数在范围 [1, 100] 内
  • 0 <= Node.val <= 9
  • 题目数据保证列表表示的数字不含前导零

方法一：模拟加法（推荐）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* p = &dummy;
        int carry = 0;
        while (l1 || l2 || carry) {
            int x = l1 ? l1->val : 0;
            int y = l2 ? l2->val : 0;
            int sum = x + y + carry;
            carry = sum / 10;
            p->next = new ListNode(sum % 10);
            p = p->next;
            if (l1) l1 = l1->next;
            if (l2) l2 = l2->next;
        }
        return dummy.next;
    }
};
  • 执行用时： O(max(m, n))
  • 空间复杂度： O(max(m, n))

思路：
逐位相加并维护进位，利用哑节点简化链表操作。该方法所有运算均发生在寄存器和简单指针运算层面，仅在创建新节点时触发堆分配，性能稳定，推荐首选。

方法二：递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    ListNode* add(ListNode* l1, ListNode* l2, int carry) {
        if (!l1 && !l2 && carry == 0) return nullptr;
        int x = l1 ? l1->val : 0;
        int y = l2 ? l2->val : 0;
        int sum = x + y + carry;
        ListNode* node = new ListNode(sum % 10);
        node->next = add(l1 ? l1->next : nullptr,
                         l2 ? l2->next : nullptr,
                         sum / 10);
        return node;
    }

    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        return add(l1, l2, 0);
    }
};
  • 执行用时： O(max(m, n))
  • 空间复杂度： O(max(m, n))（递归栈空间）

思路：
将每一位相加的逻辑递归下沉，递归栈负责维护进位和返回，代码简洁。但受限于系统栈深度，不宜用于特别长的链表。

方法三：使用栈（适用于正序存储）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    ListNode* reverse(ListNode* head) {
        ListNode* prev = nullptr;
        while (head) {
            ListNode* nxt = head->next;
            head->next = prev;
            prev = head;
            head = nxt;
        }
        return prev;
    }
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        l1 = reverse(l1);
        l2 = reverse(l2);
        std::stack<int> s1, s2;
        while (l1) { s1.push(l1->val); l1 = l1->next; }
        while (l2) { s2.push(l2->val); l2 = l2->next; }

        int carry = 0;
        ListNode* head = nullptr;
        while (!s1.empty() || !s2.empty() || carry) {
            int x = s1.empty() ? 0 : s1.top(); if (!s1.empty()) s1.pop();
            int y = s2.empty() ? 0 : s2.top(); if (!s2.empty()) s2.pop();
            int sum = x + y + carry;
            carry = sum / 10;
            ListNode* node = new ListNode(sum % 10);
            node->next = head;
            head = node;
        }
        return reverse(head);
    }
};
  • 执行用时： O(m + n)
  • 空间复杂度： O(m + n)

思路：
先反转链表至正序，利用显式栈缓存各位数字，再完成加法后恢复逆序。适合链表已正序存储或需保留原链表不变的场景。

算法底层原理与性能优化

寄存器与内存分配

  • 简单整数加法与指针操作均在 CPU 寄存器中完成，流水线友好。
  • 堆上对象（ListNode）频繁分配会产生系统调用开销，可通过对象池复用减少成本。

递归栈 vs 显式栈

  • 递归受限于系统栈深度且每层额外保存返回地址及参数；显式栈分配更可控且缓存局部性更好。

缓存局部性与对象池

  • 链表节点散落在堆中，容易发生缓存未命中；使用对象池可集中分配、提高缓存命中率。

并行化思考

  • 对于超长向量加法，可考虑 SIMD；链表场景下收益有限，通常不建议。

模拟加法（迭代）流程图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
+---------------------------+
|    开始 addTwoNumbers     |
+------------+--------------+
             |
             v
+------------+--------------+
| 初始化 dummy, p, carry=0  |
+------------+--------------+
             |
             v
+------------+--------------+
| l1/l2 任一不空或 carry=1? - No -> 返回 dummy.next
+------------+-+------------+
             |
            Yes
             |
             v
+------------+--------------+
| x = l1?l1->val:0, y = ...  |
+------------+--------------+
             |
             v
+------------+--------------+
| sum = x+y+carry           |
+------------+--------------+
             |
             v
+------------+--------------+
| carry = sum/10            |
+------------+--------------+
             |
             v
+------------+--------------+
| 新节点 val=sum%10         |
+------------+--------------+
             |
             v
+------------+--------------+
| p->next=node; p=node      |
+------------+--------------+
             |
             v
+------------+--------------+
| l1?l1=l1->next, l2同理    |
+------------+--------------+
             |
             v
           重复循环

对象池优化示例（伪码）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class ListNodePool {
    std::vector<ListNode*> pool;
public:
    ListNode* alloc(int v) {
        if (!pool.empty()) {
            auto node = pool.back(); pool.pop_back();
            node->val = v; node->next = nullptr;
            return node;
        }
        return new ListNode(v);
    }
    void release(ListNode* node) {
        pool.push_back(node);
    }
};

ListNode* fastAdd(ListNode* l1, ListNode* l2) {
    ListNodePool pool;
    ListNode dummy(0), *p = &dummy;
    int carry = 0;
    while (l1 || l2 || carry) {
        int sum = (l1?l1->val:0) + (l2?l2->val:0) + carry;
        carry = sum / 10;
        auto node = pool.alloc(sum % 10);
        p->next = node; p = node;
        if (l1) l1 = l1->next;
        if (l2) l2 = l2->next;
    }
    return dummy.next;
}

作者想说的话：
“两数相加”作为链表模拟经典题，不仅要掌握三种常见解法，更需理解底层运行原理与优化思路，才能在面试和工程实践中游刃有余。

推荐拓展练习：力扣 445. 两数相加 II（正序版本）。