LeetCode 2 — 两数相加（Add Two Numbers） 笔记

1. 题目描述

给定两个非空链表 l1 和 l2，它们表示两个非负整数。数字以 逆序 方式存储，每个节点只存储一位数字。请将两个数相加，并以相同形式返回一个表示和的链表。

示例：

输入：l1 = [2 -> 4 -> 3],  l2 = [5 -> 6 -> 4]
输出：[7 -> 0 -> 8]    // 342 + 465 = 807

2. 虚拟头节点（dummy）的作用

使用一个 栈上 的 dummy 节点，可以简化链表构造：

ListNode dummy(0);
ListNode* cur = &dummy;

1. 统一插入逻辑：无需区分第一个节点和后续节点，所有插入都用 cur->next = ...。
2. 简化返回：最终结果链表头为 dummy.next，无须额外空指针判断。
3. 避免空指针：dummy 永远存在，cur 始终有效。
4. 自动回收：dummy 在函数结束时自动销毁，无需 delete。

3. 栈上 vs 堆上 分配

• dummy：只在当前函数中临时占位，用栈对象最简单。
• 实际节点：链表长度未知、需跨函数返回，用 new 在堆上分配。

4. ListNode vs ListNode* 何时使用

• 值对象 (ListNode)：

  • 临时、固定数量，生命周期仅限当前作用域。
  • 示例：ListNode temp(5);

• 指针 (ListNode*)：

  • 动态增删、跨函数使用的链表节点。

  • 示例：

    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    

原则：

需要跨函数传递或动态控制节点数，使用堆分配和指针；仅本地临时使用，使用栈对象。

5. 代码实现与修正

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* cur = &dummy;
        int carry = 0;

        // 核心：使用 while 而非 if，处理所有节点和进位
        while (l1 || l2 || carry) {
            int sum = carry;
            if (l1) {
                sum += l1->val;
                l1 = l1->next;
            }
            if (l2) {
                sum += l2->val;
                l2 = l2->next;
            }

            carry = sum / 10;
            cur->next = new ListNode(sum % 10);
            cur = cur->next;
        }

        return dummy.next;
    }
};

修正要点：

• 循环条件要 while(l1 || l2 || carry)，而非 if，以便处理所有位。
• 将 curry 更正为 carry，语义更清晰。

以上内容即本题核心思路与实现要点。

6. 输入输出格式

输入：两个链表头指针 l1 和 l2，分别表示两个逆序存放的非负整数的位序列。

例如：l1 = [2,4,3] 对应数字 342； l2 = [5,6,4] 对应数字 465。

输出：返回一个链表头指针，指向表示两数之和的逆序链表。

对应上例，输出链表为 [7,0,8]，表示数字 807。

代码模板：

#include <bits/stdc++.h>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 从向量创建链表（逆序）
ListNode* createList(const vector<int>& v) {
    ListNode dummy(0);
    ListNode* cur = &dummy;
    for (int x : v) {
        cur->next = new ListNode(x);
        cur = cur->next;
    }
    return dummy.next;
}

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* cur = &dummy;
        int carry = 0;
        while (l1 || l2 || carry) {
            int sum = carry;
            if (l1) { sum += l1->val; l1 = l1->next; }
            if (l2) { sum += l2->val; l2 = l2->next; }
            carry = sum / 10;
            cur->next = new ListNode(sum % 10);
            cur = cur->next;
        }
        return dummy.next;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n1;
    cin >> n1;
    vector<int> v1(n1);
    for (int i = 0; i < n1; ++i) cin >> v1[i];

    int n2;
    cin >> n2;
    vector<int> v2(n2);
    for (int i = 0; i < n2; ++i) cin >> v2[i];

    ListNode* l1 = createList(v1);
    ListNode* l2 = createList(v2);

    Solution sol;
    ListNode* res = sol.addTwoNumbers(l1, l2);

    // 输出结果
    bool first = true;
    while (res) {
        if (!first) cout << ' ';
        first = false;
        cout << res->val;
        res = res->next;
    }
    cout << '
';
    return 0;
}