链表相加：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
6. 多语言最简实现（工程可用）
Python（易读清爽）
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode()
cur = dummy
carry = 0
while l1 or l2 or carry:
x = l1.val if l1 else 0
y = l2.val if l2 else 0
s = x + y + carry
cur.next = ListNode(s % 10)
carry = s // 10
cur = cur.next
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
return dummy.next
Java（面试常用）
class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
int carry = 0;
while (l1 != null || l2 != null || carry != 0) {
int x = (l1 != null) ? l1.val : 0;
int y = (l2 != null) ? l2.val : 0;
int sum = x + y + carry;
cur.next = new ListNode(sum % 10);
carry = sum / 10;
cur = cur.next;
l1 = (l1 != null) ? l1.next : null;
l2 = (l2 != null) ? l2.next : null;
}
return dummy.next;
}
}
JavaScript（前端/面试双场景）
function ListNode(val, next) {
this.val = (val === undefined ? 0 : val);
this.next = (next === undefined ? null : next);
}
function addTwoNumbers(l1, l2) {
const dummy = new ListNode();
let cur = dummy, carry = 0;
while (l1 || l2 || carry) {
const x = l1 ? l1.val : 0;
const y = l2 ? l2.val : 0;
const sum = x + y + carry;
cur.next = new ListNode(sum % 10);
carry = Math.floor(sum / 10);
cur = cur.next;
l1 = l1 ? l1.next : null;
l2 = l2 ? l2.next : null;
}
return dummy.next;
}
C++（效率党友好）
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 (l1 || l2 || carry) {
int x = l1 ? l1->val : 0;
int y = l2 ? l2->val : 0;
int sum = x + y + carry;
cur->next = new ListNode(sum % 10);
carry = sum / 10;
cur = cur->next;
l1 = l1 ? l1->next : nullptr;
l2 = l2 ? l2->next : nullptr;
}
return dummy.next;
}
};
7. 复杂度与正确性（知其所以然）
- 时间复杂度：O(n + m)，n、m 分别是两条链表长度——每个节点只访问一次。
- 空间复杂度：O(1) 额外空间（不计输出链表）。只维护常数级指针与 carry。
- 正确性关键：
- 不对齐也能相加：把空位置当 0 即可；
- carry 能把'溢出'持续传递到更高位；
- 循环条件包含 carry，保证最后一位进位不丢。
8. 边界与易错点（踩坑清单）
- 两表长度不同：注意短的用 0 填充。
- 全 0：输入 [0] 和 [0] 直接返回 [0]。
- 最后一位仍有进位：别忘了补一个 1。
- 结构复用：不要把输入链表'就地改'，面试里更稳妥的是新建节点。
- 变量命名与风格：dummy、cur、carry 这组命名清晰易懂，避免复杂缩写。
9. 工程最佳实践（代码质量）
- 统一使用'哑结点'简化头插逻辑；
- 将'取节点值或 0'的逻辑集中到循环内，减少 if-else 嵌套；
- 循环条件写成'l1 || l2 || carry'，天然覆盖收尾进位；
- 语言选择上，Java/C++ 注意 new 节点与指针移动；
- 写完后用 3 个样例回归（题目示例），确保健壮。
10. 进阶变体（打破思维定式）
- 变体 A：如果链表为'正序'（高位在前）——需先反转链表再做同样运算，或用栈把数字倒出来。
- 变体 B：支持负数——常见做法是用'符号 + 绝对值'的结构，先处理符号，再做加减。
- 变体 C：k 个链表相加——可用小顶堆按节点位权合并，或两两合并迭代。
11. 经典案例复盘（从题设到落地）
- 示例 1：l1=[2,4,3], l2=[5,6,4]（342 + 465 = 807）
- 位 1：2+5=7（写 7，carry=0）
- 位 2：4+6=10（写 0，carry=1）
- 位 3：3+4+1=8（写 8，carry=0）⇒ 结果 [7,0,8]
- 示例 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]
12. 相关权威资料与参考文献
- LeetCode：Add Two Numbers（Problem 2）
- CLRS《算法导论》（第 4 版）（第 2 章：算法基础与加法思维）
- Algorithms, 4th Edition 官方网站（链表与数据结构章节）
- MIT 6.006 Introduction to Algorithms（OCW）
- Google Java Style Guide
13. 速记口诀与系统性认知
口诀：
- '珠串相加逢十进一，短缺补零指针齐移；哑头接果收尾补一，carry 不空循环继续。'
思维导图回顾：
- 问题建模：大整数 → 倒序链表
- 核心机制：逐位相加 + 进位传递
- 代码骨架：dummy / cur / carry 三件套
- 质量保证：三示例回归 + 边界清单
- 触类旁通：正序链表、k 路相加、带符号扩展
