链表相加：LeetCode 两数相加算法详解
1. 概述（What & Why）
- 题目要点：给定两个非空单链表，表示两个非负整数。每个节点只存一个数字，且以'逆序'存储（低位在前）。返回相同形式的和。
- 输入示例：l1 = [2,4,3] 表示 342；l2 = [5,6,4] 表示 465。输出 [7,0,8] 表示 807。
- 这题考察：
- 链表遍历与节点拼接（指针基础）
- 进位（carry）处理
- 边界条件（长度不等、最后仍有进位）
- 为什么重要：
- 面试高频：考指针功底、编码规范、思维严谨
- 工程常见：财务流水相加、长整型大数计算、分布式分片结果合并
2. 简介与项目背景（Scenario）
设想你要在一台内存有限的设备上处理超大整数（长度上千位），无法直接用内置整型。常见做法是把每一位拆开，用链表（或数组）存储，再像人手算一样'逐位相加、逢十进一'。本题正是这个过程的程序化版本。
3. 名词解释（让外行也能懂）
- 单链表（Singly Linked List）：像一串珠子，每颗珠子（节点）里有一个数字和指向下一颗珠子的线。只能按照一个方向走。
- 逆序存储：最低位在链表头部。就像你把账本倒着记，先写个位，再写十位。
- 进位（carry）：两数相加超过 9，就把十位'进'到下一位。手算 8+9=17，写 7，进 1。
- 哑结点（dummy head）：一个'占位头'，真实结果从它后面开始，便于统一处理链表头的插入。
用生活类比总结：两个人各拿了一串'倒着写的账本'，你从左到右各取一颗珠子相加，超过 9 就往下一颗里'塞 1'。直到两串都走完了，还要检查手里是否还拎着一个进位。
4. 流程图（Mermaid）
graph TD
Start[开始] --> Cond{l1 或 l2 是否为空？}
Cond -- 否 --> GetVal[取出 x=l1.val 或 0<br>取出 y=l2.val 或 0]
GetVal --> Calc[sum = x + y + carry]
Calc --> Node[新节点写入 sum%10]
Node --> CheckNext{是否还有 l1/l2?}
CheckNext -- 是 --> Move[指针右移 l1=l1.next<br>l2=l2.next]
Move --> LoopEnd{循环结束？}
LoopEnd -- 否 --> Cond
LoopEnd -- 是 --> CheckCarry{carry 是否为 1?}
CheckCarry -- 是 --> AddOne[补一个值为 1 的节点]
AddOne --> End[返回 dummy.next]
CheckCarry -- 否 --> End
Cond -- 是 --> LoopEnd
5. 核心算法（口述到代码）
口述版：
- 用一个'哑结点'接住结果，另设 cur 指向它；carry 初值为 0。
- 循环：取 l1、l2 当前节点的值（空则记 0），与 carry 相加得 sum；
- 新建节点写入 sum % 10；
- carry = Math.floor(sum / 10)；
- l1、l2 指针右移；
- 循环结束后如果 carry 仍为 1，再补一个值为 1 的节点；返回哑结点的 next。
伪代码（接近任何语言都能落地）：
while (l1 != null || l2 != null || carry != 0) {
x = (l1 != null) ? l1.val : 0
y = (l2 != null) ? l2.val : 0
sum = x + y + carry
cur.next = new ListNode(sum % 10)
carry = sum / 10
if (l1) l1 = l1.next
if (l2) l2 = l2.next
cur = cur.next
}
return dummy.next
