1. 题目到底在考什么1.1 从“两数相加”看链表的真实用法“链表(两数相加)”这个标题其实是数据结构与算法里一道非常经典的问题给你两个非空的链表每个链表代表一个非负整数数字的每一位按逆序方式存储在链表节点中请你把两个数相加并返回一个新的链表来表示它们的和。我第一次刷这道题的时候第一反应是“这不就是小学加法吗”确实本质就是竖式加法。但真正动手写代码之后才发现这道题考察的东西远比“会加法”要多。它要求你对链表的基本操作——遍历、取值、创建新节点、处理边界情况——都有扎实的掌握同时还要能处理进位、不同长度链表对齐、最后一位的额外进位等诸多细节。对新手来说这道题是一道很好用的“体检题”你自认为链表学得不错写一遍这道题就知道哪里还有漏洞。对准备面试的开发者来说这道题也是高频题几乎每家公司在考察基础数据结构时都会拿它出来做试金石。所以这篇博文会围绕这道题把链表的核心知识点从头到尾串一遍既有可以直接抄走的代码也有实操中容易踩的坑。1.2 一道题能串起来的基础知识点这道题表面上只是“两数相加”但把它拆开来看你会发现它串起了一大串链表基础知识点这也正是为什么它值得认真写一遍链表节点的定义方式涵盖结构体、指针、构造函数带头结点和不带头结点的区别与影响链表的遍历方式包括循环遍历和指针移动链表的插入操作包括尾部追加新节点的写法链表长度不同时的边界处理递归思路和迭代思路的对比。后面我会按实际动手的顺序来展开从定义链表节点开始到实现两数相加的核心方法再到进阶变体和排错经验。整个过程都是我实际刷题、写代码时反复整理过的路线跟着走一遍你对链表的理解会比只看教材深刻得多。2. 动手之前先把“节点”这张底牌摸清2.1 C里链表节点到底怎么定义很多人看到链表题目直接就开写算法结果卡在最基础的环节节点怎么定义构造函数里参数怎么写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) {} };这里有几个细节值得注意val存的是当前位的数字next指向下一个节点三个构造函数分别对应“空节点”、“只给值”、“给值和下一个节点”三种场景。实际写题时ListNode(x)用得最多因为我们要不断地创建新节点来保存每一位的和next一定要初始化为nullptr否则会有不可预测的野指针问题这在嵌入式开发中更严重可能导致硬件异常。很多初学者会问为什么节点还要写构造函数直接用结构体不行吗行是行但每次创建一个节点都要手动node-next NULL来初始化非常容易漏。自己写代码可以随性但面试或工程实践中工整的构造定义会让代码的可读性和安全性高很多。我个人的习惯是不管题目的运行环境是否默认提供了ListNode定义我在本地练习时都自己写一遍完整定义这也算是对链表基本功的日常训练。2.2 带头结点与不带头结点的区别热词里有一个词条叫“不带头结点的单链表”它和“带头结点的单链表”是一个很多初学者搞不清的经典纠结。简单说明一下区别带头结点的链表有一个额外的头节点通常val不存数据真正的数据从第二个节点开始。它的好处是空表和非空表的操作逻辑统一插入删除不需要特殊处理“表头为空”的情况。不带头结点的链表第一个节点就存数据链表为空时head直接是nullptr。“两数相加”这道题默认给的链表是不带头结点的因为第一个节点存的就是最低位数字比如数字 342 表示为 2 - 4 - 3。这意味着你在处理结果链表时要特别注意头节点为空的情况。我在实际写代码时通常用的办法是创建一个**哑节点dummy node**作为结果链表的头最后返回dummy.next。这个套路其实就是“带头结点思想在算法题中的应用”它可以让你免去“结果链表是否为空”的判断直接往尾部追加节点就行。后面第 3 章的代码里我用的就是这个思路这也是面试中很常见、很被认可的写法。2.3 链表的插入、遍历这些基本操作为什么和这道题强相关“两数相加”的核心操作可以归纳成两件事同时遍历两个输入链表逐位取值把每一位的和作为一个新节点插入到结果链表的尾部。所以这道题直接考察了“链表遍历”和“链表插入尾插法”两个基本操作。很多新手写遍历时习惯写while (p ! NULL)然后p p-next;这个没问题。但等两个链表长度不一致时遍历的写法就需要更细致的判断比如其中一个链表已经走完了另一个还有节点此时要把它当成 0 处理int x (l1 ! nullptr) ? l1-val : 0; int y (l2 ! nullptr) ? l2-val : 0;这种“短链表补 0”的技巧非常实用也是这道题最重要的细节之一。还有尾插法的实现很多人每一步都用一个临时指针tail tail-next来追加节点这个模式在“两数相加”这道题里会完整地走一遍写完这道题后你对尾插法会有肌肉记忆。3. 核心解法拆解从拆解步骤到代码实现3.1 解法思路——把加法还原成手算过程这道题的解题思路不需要任何高深算法就是还原手算加法的过程。回想一下小学学加法的时候你会把两个数从个位开始一列一列地对齐相加满十进一。链表存储刚好是逆序的第一个节点就是个位第二个节点是十位第三个节点是百位……这对我们非常友好直接从链头开始往后走就是在从个位往高位计算。整个过程手动模拟一遍以 342 465 807 为例链表12 - 4 - 3代表 342链表25 - 6 - 4代表 465个位2 5 7无进位十位4 6 10写 0进 1百位3 4 1进位 8无进位结果7 - 0 - 8代表 807。注意十位这里46 本身是 10但一位节点只能存一个数字所以只能存 0把进位 1 加到高位上。这个“进位累积”是整个算法的灵魂。3.2 关键步骤循环条件、进位处理、结果构建实现时的三个关键点循环条件不能只写while (l1 ! nullptr l2 ! nullptr)因为两个链表长度可能不一样。正确写法是while (l1 ! nullptr || l2 ! nullptr)在循环体内部用条件表达式把已经为空的链表视为 0。进位处理用一个carry变量记录进位。每轮循环把sum x y carry算出来当前位的值是sum % 10新的进位是sum / 10。循环结束后还要检查一下carry是否仍为 1如果有还要再追加一个值为 1 的节点。结果构建创建哑节点dummyHead用一个tail指针始终指向结果链表的尾节点每次创建新节点后移动tail。补充说明一下“循环结束后检查进位”的必要性举一个典型的例子链表1 是 9 - 9链表2 是 1相加过程是 9110 写 0 进 1下一位 90110 写 0 进 1循环结束时链表1、链表2都已经走完但carry还是 1。如果你不追加这个最后的节点结果就会从 100 变成 00这是这道题一个非常经典的失误点。3.3 完整代码实现C与Python双版本先看 C 版本的完整实现class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* dummyHead new ListNode(0); ListNode* tail dummyHead; int carry 0; while (l1 ! nullptr || l2 ! nullptr) { int x (l1 ! nullptr) ? l1-val : 0; int y (l2 ! nullptr) ? l2-val : 0; int sum x y carry; carry sum / 10; tail-next new ListNode(sum % 10); tail tail-next; if (l1 ! nullptr) l1 l1-next; if (l2 ! nullptr) l2 l2-next; } if (carry 0) { tail-next new ListNode(carry); tail tail-next; } return dummyHead-next; } };再看 Python 版本class ListNode: def __init__(self, val0, nextNone): self.val val self.next next class Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) - ListNode: dummy ListNode(0) tail dummy carry 0 while l1 or l2: x l1.val if l1 else 0 y l2.val if l2 else 0 total x y carry carry total // 10 tail.next ListNode(total % 10) tail tail.next if l1: l1 l1.next if l2: l2 l2.next if carry 0: tail.next ListNode(carry) return dummy.next两个版本逻辑完全一致。Python 版本在定义节点时比 C 简洁一些但核心的“哑节点 尾插法 进位传递”完全一样。我建议你在本地分别用两门语言各写一遍感受一下语言对链表表达方式的差异这对以后灵活应对不同岗位的面试题很有帮助。3.4 时间复杂度和空间复杂度分析这个问题面试时几乎必问所以提前把复杂度分析想清楚时间复杂度O(max(m, n))其中 m 和 n 分别是两个链表的长度。因为循环要一直持续到较长的链表遍历完所以整体耗跟随较长链表的长度线性增长。每个节点只被访问常数次所以这个复杂度是必然的也是最优的。空间复杂度O(max(m, n))。如果只考虑额外空间不算输出链表是 O(1)因为只用了dummyHead、tail、carry几个变量。但如果连同输出结果链表一起看那么新链表最多有 max(m, n) 1 个节点所以总空间是 O(max(m, n))。这里有一个容易搞混的点很多答案说空间复杂度 O(1)指的是“额外辅助空间”O(1)而结果链表本身就是题目要求的输出不算额外空间。跟面试官聊的时候建议明确表达“辅助空间是 O(1)输出链表空间不算”这样显得你考虑问题更全面。4. 进阶视角与变体延展4.1 递归解法换一种思路理解链表遍历除了迭代这道题也能用递归来写而且递归写起来非常紧凑。递归的思路是先把当前位的数字相加计算出进位再递归处理下一对节点等递归返回后把进位加到返回结果的当前位上。一个常见的递归写法如下class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2, int carry 0) { if (l1 nullptr l2 nullptr carry 0) { return nullptr; } int x (l1 ! nullptr) ? l1-val : 0; int y (l2 ! nullptr) ? l2-val : 0; int sum x y carry; carry sum / 10; ListNode* result new ListNode(sum % 10); result-next addTwoNumbers( (l1 ! nullptr) ? l1-next : nullptr, (l2 ! nullptr) ? l2-next : nullptr, carry ); return result; } };注意递归的终止条件是l1 nullptr l2 nullptr carry 0比迭代版本多考虑了“没有剩余节点但仍有进位”的情况。递归优点是好理解、代码简洁缺点是当链表特别长时有栈溢出的风险。在实际工程或嵌入式环境下递归往往比迭代更危险所以我在面试时会更倾向于先答迭代再补充说明递归思路展示两种解法的权衡能力。4.2 大数相加的扩展链表存储长整数方案这道题的一个直接扩展是如果用链表存储一个超长的整数比如上千位不能直接用整数类型存储该怎么办这时链表就非常有用了。因为传统的 int、long long 在大数面前都有位数上限而链表可以动态增长每一位单独存储只受内存限制。我在嵌入式开发中见过类似的场景读取传感器数据后需要把多个字节的数值合并成一个大整数而这个大整数可能超过标准类型的表示范围此时就可以用链表或数组来逐位存储。这种场景下链表的好处是内存分配灵活、插入高位方便代价是访问某个中间位的代价比数组高必须从头遍历。所以在“两数相加”中用链表其实是很合适的——两个数都是正序或逆序存储遍历顺序与计算顺序一致不会有随机访问需求。如果你想把这个扩展想得更深一点可以试试“链表大数乘法”把两数相加的逐位运算换成乘法加错位累加。这个变体会引入更多关于“错位”“补零”的细节比单纯相加有意思得多也是对链表操作更深层的应用。4.3 循环单链表、逆置链表等关联知识点热词里出现了“循环单链表”“Python单链表逆序”“逆置链表”这些词它们跟“两数相加”虽然不是同一道题但都属于链表这一类的核心操作。我建议把它们作为一组练习题放在一起刷逆置链表反转一个单链表。这个操作在不少考题中是基础比如判断回文链表时需要先找到中点再逆置后半段。单链表逆序Python递归或迭代实现逆序递归写法很考验对递归栈的理解。循环单链表尾节点指向头节点常用于约瑟夫环、循环队列等场景。它的遍历终止条件不再是p nullptr而是p head“两数相加”中并不涉及循环链表的操作但你需要能区分什么时候用普通单链表什么时候用循环链表。我把这几道关联题放在一起练的原因是它们都用到了“指针引用”“逐个节点操作”的核心思想但又各有侧重。“两数相加”练的是同时操作两个链表“逆置链表”练的是指针方向的改变“循环链表”练的是边界条件的判定。串起来练一遍你对链表这一整个知识域的理解会非常完整。5. 常见问题与排查技巧实录5.1 写了两数相加之后我踩过的坑这道题我在不同时期写过好几遍也帮不少初学者看过代码总结出了一些高频错误。先说一个最典型的循环条件写成了while (l1 ! nullptr l2 ! nullptr)。这样写会导致两个链表长度不同时循环提前结束较长的链表后面几位直接丢失。比如1 - 2 - 3和1 - 2正确结果应该处理三位但这个错误写法只处理了两位。正确写法是用||并在循环体内部对空链表补 0。第二个高频错误是忽略了最后的进位。刚才已经举过 99 1 的例子carry在循环结束后仍为 1没有追加节点导致结果少了最高位。这个问题我在代码审查中见过不下五次印象非常深刻。第三个错误是移动链表指针时没判断空。很多人写完l1 l1-next;之后才意识到此时l1可能已经是nullptr再取l1-val就会直接报空指针异常。正确做法是每次移动前先判断当前节点是否为空。第四个问题相对隐蔽在 C 中多次创建新节点时没有注意内存释放。严格来说在线判题系统里节点内存由系统统一回收不释放问题不大但如果在本地做内存检测比如 Valgrind就会报泄漏。工程上更稳妥的做法是在合适时机遍历结果链表释放节点尤其是你自己写的工具函数里涉及链表创建时。5.2 现场调试与自测用例设计现场写这道题时建议准备几个自测用例快速验证代码边界是否正确测试场景输入期望输出验证重点普通场景342 465807基本功能长度不同9 99108短链表补0进位连续999 11000循环结束后仍有进位结果为00 00多位链表中的0值处理大数场景长度超过10的链表相加逐位正确结果长链表稳定性调试时我有一个个人习惯把一个“打印链表”的函数先写好。它足够简单但能让你在每一步之后立刻看到当前链表的内容void printList(ListNode* head) { while (head ! nullptr) { std::cout head-val - ; head head-next; } std::cout nullptr std::endl; }别小看这个打印函数它能帮你快速定位是“哪一步开始结果不对”的。比如把进位打印出来、把每一步的 sum 打印出来基本上一眼就能看出问题出在取值还是进位还是节点连接顺序上。这个“分段调试”的习惯比一口气读完整个代码找 bug 高效得多。5.3 常见问题速查表下面这张表整理了“两数相加”和相关链表操作中提问频率较高的问题附上排查思路方便你在实际练习中对照使用。现象可能原因排查方向结果链表少了高位循环结束后没有追加进位节点检查循环结束后carry 0的处理逻辑输出结果位数不够循环条件用导致短链表提前退出改为 while (l1运行时报空指针异常移动指针后直接访问val未判空在访问l1-val前先判断l1 ! nullptr结果链表顺序反了把新节点插到了头部而不是尾部检查是否用了尾插法保留 tail 指针内存泄漏创建了新节点但没有释放在本地测试中用内存检测工具检查循环单链表出现死循环遍历条件写成了p ! nullptr但尾节点指向头判断循环链表的终止条件应为p ! head5.4 面试中的补充经验最后分享一点面试相关的实操经验。如果面试官让你写“两数相加”不要上来就闷头写代码可以先花 30 秒快速说思路“我准备从最低位开始逐位相加用一个变量保存进位结果用哑节点构建新链表。”这几句话能让面试官知道你对这个模型的整体把握也能给自己理清思路。写完代码后建议主动说复杂度分析先讲时间 O(max(m,n))再讲辅助空间 O(1)同时说明输出链表不计入额外空间。面试官往往更看重你是否具备“分析权衡”的意识而不仅是把代码写出来。还有一个小技巧在“链表”这类题目中“哑节点”几乎是万能的辅助技术。不管是在链表头部插入新节点还是需要统一处理空链表创建一个dummy节点都能让逻辑变得整洁很多。这道题里用它逆置链表里也能用它合并有序链表里同样能用。练通了这一招很多链表题会一下子简单不少。我个人在这道题上反复练了很多遍之后的体会是链表题考察的从来不是“你会不会设计算法”而是“你对指针/引用的操作是否足够扎实”。两数相加本身不复杂但当你把边界处理、进位传递、哑节点这些细节都能一次写对你对链表的手感就基本到位了。后续再去刷逆置链表、合并有序链表、判断回文链表等题目你会明显体会到基础这关过了之后进阶题都是在这些基础操作上叠加变化而已。