链表两数相加算法详解（C++ 实现）

一、问题剖析：两数相加究竟是什么？

在数据结构场景下，两数相加通常指两个非空链表分别表示两个非负整数。链表中的每个节点只存储一位数字，且按逆序方式排列。任务是将这两个数相加，并以相同逆序的链表形式返回和。

例如：链表 1 为 2 -> 4 -> 3（代表 342），链表 2 为 5 -> 6 -> 4（代表 465）。相加结果为 807，对应返回链表应为 7 -> 0 -> 8。

采用逆序存储是为了方便从最低位（个位）开始进行加法操作，模拟手工计算过程，便于处理进位。

二、实现思路：一步步拆解问题

1. 初始化相关变量 创建一个新的链表存储结果，使用虚拟头节点（哨兵节点）简化操作。定义指针指向当前新链表末尾，以及记录进位值的变量（初始为 0）。

2. 遍历两个链表进行相加 同时遍历两个输入链表，获取当前节点值。若某链表已遍历结束，其当前节点值视为 0。将两值与进位值相加得到总和。

3. 计算当前位数字和新的进位值 当前位数字为总和对 10 取余，新进位值为总和除以 10 取整。

4. 添加新节点到结果链表 创建新节点存储当前位数字，添加到结果链表末尾，移动末尾指针。C++ 中需使用 new 动态分配内存。

5. 处理链表遍历结束后的进位 若遍历结束后进位值不为 0，需在结果链表末尾新增节点存储该进位值。

6. 返回结果链表 返回虚拟头节点的下一个节点作为结果链表的第一个有效节点。

三、代码实现：用 C++ 语言实战

#include <iostream>
using namespace std;

// 链表节点定义
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) {}
};

// 核心函数：两数相加
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    // 虚拟头节点
    ListNode* dummy = new ListNode(0);
    ListNode* cur = dummy;
    int carry = 0;

    // 只要有一个链表没遍历完，或还有进位，就继续算
    while (l1 != nullptr || l2 != nullptr || carry != 0) {
        int num1 = (l1 != nullptr) ? l1->val : 0;
        int num2 = (l2 != nullptr) ? l2->val : 0;
        int sum = num1 + num2 + carry;
        carry = sum / 10;
        int curVal = sum % 10;

        cur->next = new ListNode(curVal);
        cur = cur->next;

        if (l1 != nullptr) l1 = l1->next;
        if (l2 != nullptr) l2 = l2->next;
    }

    ListNode* result = dummy->next;
    delete dummy;
    return result;
}

// 辅助函数：打印链表
void printList(ListNode* head) {
    while (head != nullptr) {
        cout << head->val;
        if (head->next != nullptr) cout << " -> ";
        head = head->next;
    }
    cout << endl;
}

// 测试代码
int main() {
    // 构建链表 1：2 -> 4 -> 3
    ListNode* l1 = new ListNode(2);
    l1->next = new ListNode(4);
    l1->next->next = new ListNode(3);

    // 构建链表 2：5 -> 6 -> 4
    ListNode* l2 = new ListNode(5);
    l2->next = new ListNode(6);
    l2->next->next = new ListNode(4);

    // 计算并输出结果
    ListNode* res = addTwoNumbers(l1, l2);
    cout << "结果链表：";
    printList(res);

    // 释放内存
    delete l1->next->next; delete l1->next; delete l1;
    delete l2->next->next; delete l2->next; delete l2;
    delete res->next->next; delete res->next; delete res;

    return 0;
}

四、实战技巧与注意事项

1. 处理链表为空的情况（nullptr 判断）

C++11 及以后标准推荐使用 nullptr。在核心函数中，若链表遍历到末尾（指针为 nullptr），将当前值视为 0 参与计算，避免直接访问触发空指针崩溃。

2. 进位的处理要彻底

进位是链表加法最容易出错的点。不仅遍历过程中要传递进位，遍历结束后若进位不为 0，必须新增节点存储。循环条件应包含 carry != 0。

3. 虚拟头节点的使用

使用 dummy 节点可简化逻辑，无需判断结果链表是否为空。所有新节点统一挂在 cur->next 上，最后返回 dummy->next。注意手动释放虚拟头节点内存。

4. C++ 动态内存管理

C++ 没有自动垃圾回收，new 创建的对象必须手动 delete。建议封装 freeList 辅助函数批量释放，或从链表末尾往前删以避免内存泄漏。

5. 构造函数的合理使用

结构体定义多个构造函数可避免冗余代码，如 new ListNode(5) 即可初始化值和 next 指针。

6. 代码可读性与规范性

• 指针命名见名知意（如 cur, dummy）。
• 遵循 C++ 规范，* 紧跟类型。
• 关键逻辑添加注释。

五、拓展与进阶

1. 链表存储数字为正序

若链表正序存储（如 3→4→2 代表 342），无法直接从表头加。可借助 C++ stack 容器，将节点值压入栈，利用栈顶为最低位的特性模拟逆序相加。

2. 处理大数相加

当数字超出 int 或 long long 范围时，链表是最优解。每个节点只存 0-9 的单个数字，逐位相加无需担心溢出。

3. 多链表相加

若需 3 个及以上链表相加，可将链表指针存入 vector<ListNode*>，遍历容器获取每一位值，避免重复写多个 if 判断。

4. 智能指针避免内存泄漏

可使用 C++11 智能指针 shared_ptr/unique_ptr 自动管理内存，降低内存泄漏风险。

六、总结

链表两数相加不仅是数据结构题，更是 C++ 核心语法的综合练习：

• 数据结构层面：掌握链表遍历、节点创建/连接、进位传递。
• C++ 语法层面：吃透指针操作、动态内存管理、结构体构造函数、容器和智能指针的使用。

建议初学者先跑通基础代码，修改测试案例验证逻辑，再尝试封装内存释放函数及实现正序链表相加。