链表相加: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

