用链表相加：从0到1彻底吃透 Add Two Numbers

Ne0inhk

— 7 min read

用链表相加：从0到1彻底吃透 Add Two Numbers

本文以 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 流程图）

下面这张带颜色样式的流程图，展示了核心步骤和关键分支：

否

是

否

是

否

开始 Start

l1 或 l2 是否为空?

取出 x=l1.val 或 0
取出 y=l2.val 或 0

sum = x + y + carry

新节点写入 sum%10

是否还有 l1/l2?

指针右移 l1=l1.next
l2=l2.next

carry 是否为 1?

补一个值为 1 的节点

返回 dummy.next

6. 核心算法（口述到代码）

口述版：

  • 用一个“哑结点”接住结果，另设 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

7. 多语言最简实现（工程可用）

Python（易读清爽）：

classListNode:def__init__(self, val=0,next=None): self.val = val self.next=nextdefaddTwoNumbers(l1: ListNode, l2: ListNode)-> ListNode: dummy = ListNode() cur = dummy carry =0while l1 or l2 or carry: x = l1.val if l1 else0 y = l2.val if l2 else0 s = x + y + carry cur.next= ListNode(s %10) carry = s //10 cur = cur.next l1 = l1.nextif l1 elseNone l2 = l2.nextif l2 elseNonereturn dummy.next

Java（面试常用）：

classListNode{int val;ListNode next;ListNode(){}ListNode(int val){this.val = val;}ListNode(int val,ListNode next){this.val = val;this.next = next;}}classSolution{publicListNodeaddTwoNumbers(ListNode l1,ListNode l2){ListNode dummy =newListNode(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 =newListNode(sum %10); carry = sum /10; cur = cur.next; l1 =(l1 !=null)? l1.next :null; l2 =(l2 !=null)? l2.next :null;}return dummy.next;}}

JavaScript（前端/面试双场景）：

functionListNode(val, next){this.val =(val===undefined?0: val)this.next =(next===undefined?null: next)}functionaddTwoNumbers(l1, l2){const dummy =newListNode()let cur = dummy, carry =0while(l1 || l2 || carry){const x = l1 ? l1.val :0const y = l2 ? l2.val :0const sum = x + y + carry cur.next =newListNode(sum %10) carry = Math.floor(sum /10) cur = cur.next l1 = l1 ? l1.next :null l2 = l2 ? l2.next :null}return dummy.next }

C++（效率党友好）：

structListNode{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){}};classSolution{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 =newListNode(sum %10); carry = sum /10; cur = cur->next; l1 = l1 ? l1->next :nullptr; l2 = l2 ? l2->next :nullptr;}return dummy.next;}};

8. 复杂度与正确性（知其所以然）

  • 时间复杂度：O(n + m)，n、m 分别是两条链表长度——每个节点只访问一次。
  • 空间复杂度：O(1) 额外空间（不计输出链表）。只维护常数级指针与 carry。
  • 正确性关键：
    • 不对齐也能相加：把空位置当 0 即可；
    • carry 能把“溢出”持续传递到更高位；
    • 循环条件包含 carry，保证最后一位进位不丢。

9. 边界与易错点（踩坑清单）

  1. 两表长度不同：注意短的用 0 填充。
  2. 全 0：输入 [0] 和 [0] 直接返回 [0]。
  3. 最后一位仍有进位：别忘了补一个 1。
  4. 结构复用：不要把输入链表“就地改”，面试里更稳妥的是新建节点。
  5. 变量命名与风格：dummy、cur、carry 这组命名清晰易懂，避免复杂缩写。

10. 工程最佳实践（代码质量）

  • 统一使用“哑结点”简化头插逻辑；
  • 将“取节点值或 0”的逻辑集中到循环内，减少 if-else 嵌套；
  • 循环条件写成“l1 || l2 || carry”，天然覆盖收尾进位；
  • 语言选择上，Java/C++ 注意 new 节点与指针移动；
  • 写完后用 3 个样例回归（题目示例），确保健壮。

11. 进阶变体（打破思维定式）

  • 变体 A：如果链表为“正序”（高位在前）——需先反转链表再做同样运算，或用栈把数字倒出来。
  • 变体 B：支持负数——常见做法是用“符号 + 绝对值”的结构，先处理符号，再做加减。
  • 变体 C：k 个链表相加——可用小顶堆按节点位权合并，或两两合并迭代。

12. 经典案例复盘（从题设到落地）

  • 示例 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]

13. 相关权威资料与参考文献

14. 速记口诀与系统性认知

口诀：

  • “珠串相加逢十进一，短缺补零指针齐移；哑头接果收尾补一，carry 不空循环继续。”

思维导图回顾：

  • 问题建模：大整数 → 倒序链表
  • 核心机制：逐位相加 + 进位传递
  • 代码骨架：dummy / cur / carry 三件套
  • 质量保证：三示例回归 + 边界清单
  • 触类旁通：正序链表、k 路相加、带符号扩展
Could not load content