【算法--链表题1】2. 两数相加：通俗详解
一、题目是啥？一句话说清
有两个链表，每个节点存储一个数字，但数字是倒着存放的（比如链表 2→4→3 表示数字 342），让你把两个链表表示的数字相加，结果也用同样的倒置链表返回。
示例：
- 输入：l1 = [2,4,3]（表示 342），l2 = [5,6,4]（表示 465）
- 输出：[7,0,8]（表示 807，因为 342 + 465 = 807）
二、解题核心
模拟手工竖式加法。就像我们在纸上从右往左逐位相加一样，算法也从链表的头部（即数字的个位）开始遍历，逐位相加，并处理进位。由于链表是逆序的，头部是个位，所以遍历顺序正好与加法顺序一致。
三、关键在哪里？（3个核心点）
想理解并解决这道题，必须抓住以下三个关键点：
1. 进位（Carry）的处理
- 是什么：进位就像“记忆器”，记录每次相加后多出来的十位数（0 或 1），并加到下一位计算中。例如，5 + 7 = 12，那么当前位写 2，进位记 1。
- 为什么重要：进位是加法的核心，忽略进位会导致结果错误。最大进位是 1（因为 9+9+1=19）。
2. 链表长度不一致的处理
- 是什么：两个数字的位数可能不同（比如 123 + 45），所以遍历时一个链表可能先结束。
- 怎么办：在循环中，如果某个链表已遍历完，则将其值视为 0 继续计算。循环条件应包含
l1 不为空或l2 不为空或进位不为 0。
3. 虚拟头节点（Dummy Node）的使用
- 是什么：一个不存储实际数据的辅助节点，作为结果链表的起点。
- 为什么有用：它简化了链表构建过程，避免处理头节点的特殊情况（比如头节点是否因进位而改变）。最后只需返回虚拟头节点的下一个节点。
四、看图理解流程（通俗理解版本）
让我们用 342 + 465 的例子来可视化过程：
-
初始化：创建虚拟头节点
dummy和当前指针curr指向它，进位carry初始为 0。dummy→NULLcarry = 0
-
计算个位（第1轮）：
- 取 l1 的个位 2，l2 的个位 5。
- 计算：
2 + 5 + 0 = 7 - 当前位：
7 % 10 = 7，进位：7 / 10 = 0 - 创建新节点 7，链接到
curr后。 - 现在链表：
dummy→7 - 移动
l1和l2到下一个节点。
-
计算十位（第2轮）：
- 取 l1 的十位 4，l2 的十位 6。
- 计算：
4 + 6 + 0 = 10 - 当前位：
10 % 10 = 0，进位：10 / 10 = 1 - 创建新节点 0，链接到链表后。
- 现在链表：
dummy→7→0 - 移动
l1和l2。
-
计算百位（第3轮）：
- 取 l1 的百位 3，l2 的百位 4。
- 计算：
3 + 4 + 1（进位） = 8 - 当前位：
8 % 10 = 8，进位：8 / 10 = 0 - 创建新节点 8，链接到链表后。
- 现在链表：
dummy→7→0→8 - 移动
l1和l2（都已为空）。
-
结束：由于
l1和l2都为空且进位为 0，循环结束。返回dummy.next（即7→0→8），表示数字 807。
五、C++ 代码实现（附详细注释）
#include <iostream>
using namespace std;