★ FEATURED ARTICLE 合并两个有序链表Merge Two Sorted List是C里再经典不过的一道链表题难度标着easy。题面短到不能再短给你两条已经升序排列的单链表把它们合并成一条新的升序链表。很多初学者一看就觉得没什么好讲双指针各扫各的谁小接谁十分钟写完提交然后等着绿色提示。可真把这题认真写一遍、再提交几轮、再帮别人review几次之后你会发现它的坑比想象中多得多——空指针崩了、返回头丢了、链表尾巴断了、甚至莫名成环了各式各样的问题都能出现。我在不少学习群和代码讨论里见过同一个现象很多已经刷到中等难度题的人回头重写这道easy题依然会漏掉某个边界分支。所以这篇文章不打算给一篇“标准答案”就收工而是把最容易犯的错挑出来逐个拆开讲清楚每个错误为什么发生、怎么定位、怎么改。无论你是刚接触链表的新手还是想在面试手撕代码前查漏补缺这份梳理都能帮你少踩几个坑。1. 为什么一道Easy题会让这么多人翻车1.1 题目表面很简单实际在考什么先别急着写代码。这道题表面上的核心是“双指针比较大小”但链表和数组最大的不同是数组有下标你可以随机访问任意位置链表只能通过指针一个接一个走下去每个节点只保存了下一个节点的地址。这意味着你不仅要选出“正确的节点”更要保证“节点之间的连接关系”完全正确。很多人在写数组版本归并时非常顺手换成链表就崩本质原因就是思维没切换过来。数组双指针合并你开一个新数组用下标写入就行链表合并里你需要自己维护一个“已经合并好的链表的末尾指针”每次把选中的节点挂到这个末尾上还要保证源链表的移动顺序正确。一个节点被接走之后它的next指针怎么处理、原链表的头指针要不要往前移动这些都是隐藏考点。这道题被标成easy考的并不是算法思想而是三样东西链表指针操作的基本功、边界条件的完备性、以及对自己代码中每一个分支的掌控力。面试场景里更明显手写代码时越简单越容易放松一旦放松空指针和断尾就找上你了。1.2 链表题和数组题的思维差异可以用一个生活场景类比想象两列人已经按身高从矮到高排好队现在要合成一列你不允许把人复制一份只能让大家重新指认“谁排在谁后面”。每个参与者手里只有一个信息——下一位是谁。链表合并就是这件事节点不能像数组元素那样复制到新位置你能做的就是不断调整next指针。数组思维带来的典型误区是“访问任意位置”“直接比较下标对应的值”。链表里没有这种东西。你拿到头节点后如果想再回头访问上一个节点除非提前用另一个指针保存否则永远找不回来。这个特性导致链表题的bug往往不是逻辑复杂而是“指针语义混乱”。所以写链表题之前必须先想清楚每个指针到底代表什么。拿这道题来说dummy是虚拟头节点tail是已合并链表的末尾l1和l2分别是两条源链表的当前候选节点。四个角色各司其职代码就不会乱。很多人写坏这道题往往是从“变量a、b、c一通乱指”开始的。2. 常见错误现场从编译报错到隐蔽逻辑坑2.1 空指针判断while(l1 || l2)为什么会崩看下面这段错误代码ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode dummy(0); ListNode* tail dummy; while (l1 || l2) { if (l1-val l2-val) { // l1 或 l2 可能为 nullptr这里直接崩 tail-next l1; l1 l1-next; } else { tail-next l2; l2 l2-next; } tail tail-next; } return dummy.next; }这段代码的问题一眼就能看出来while条件用的是l1 || l2进入循环后却直接对l1和l2都做解引用。如果其中一条链表提前空了l1-val或l2-val就是非法访问程序崩溃几乎是必然的。为什么会有人写出这种版本因为脑子里想的是“只要有一条链表没走完就得继续合并”。这句话本身没错但“继续”不等于“在两条链表都非空时比较”。更稳妥的做法是先保证两者都非空才做比较和选择循环退出后剩下的那条链表整段接上去就行。也就是说把“比较阶段”和“收尾阶段”彻底分开。空指针问题的本质是写代码前没有明确链表状态。写链表题先问自己三个问题循环进入的条件是什么循环退出时两个指针各自处于什么状态每次解引用指针之前它一定非空吗把这三个问题过一遍空指针类错误能消掉一大半。提示判断条件里如果出现l1-val l2-val这种解引用请确保l1和l2在那一刻都是非空指针。链表题的所有崩溃里这类笔误占了一半以上。2.2 循环结束后的“断尾”剩余链表去哪了另一种高频错误是循环写对了但循环结束后少了一行接尾代码while (l1 l2) { if (l1-val l2-val) { tail-next l1; l1 l1-next; } else { tail-next l2; l2 l2-next; } tail tail-next; } return dummy.next; // 少了 tail-next l1 ? l1 : l2;表面看起来代码很完整循环也退出了但结果为什么不对因为while (l1 l2)只能处理两条链表都还有节点的部分。一旦某条链表先走到头循环结束另一条链表剩下的那一段比如l1还剩[7, 9]没有人把它接到结果链表的尾部整段就丢了。为什么很多人发现不了因为测试用例里如果两条链表长度相同退出循环时两边恰好同时为空根本暴露不出这个问题。实际合并中两条链表长度差异很大才是常态一提交就发现输出少了一半。正确做法是循环之后补上这一行tail-next l1 ? l1 : l2; return dummy.next;这行代码的意思是如果l1还有剩余整段接上否则把l2剩余部分接上如果两边都为空就把tail-next置为nullptr作为合法链表结尾。这个三元表达式是安全的不会出现解引用空指针的问题可以放心写。2.3 返回值选错head、dummy、还是tail第三个常见的坑是返回了错误的节点。有人这样写ListNode* dummy new ListNode(0); ListNode* cur dummy; // 合并过程... return cur; // 错cur 此时已经在链表末尾cur在合并过程中不断往后移动最后指到链表尾部。把cur作为返回值返回等于返回了一条以尾巴为头的残缺链表前面所有节点全部丢失。还有人不用dummy试图“先比较出头节点再合并”if (!l1) return l2; if (!l2) return l1; ListNode* head l1-val l2-val ? l1 : l2;这种思路不是完全不行但后续逻辑会变得很繁琐你得小心在处理过程中不要弄丢head每次移动l1或l2后都要检查是否影响最初选出的头节点。写不了几行代码就会冒出大量重复分支非常容易出错。为什么推荐dummy虚拟头节点因为它像“队伍前的一个工作人员”。你不需要关心最终到底哪个节点会是第一个只需要让这个工作人员站在最前面所有节点排到他身后。等一切处理完毕dummy.next就是真正的链表头。这样一来所有节点的追加逻辑完全统一不用为头节点单独写判断。这是典型用微小空间换取逻辑简洁的做法。提示如果题目允许优先在栈上创建ListNode dummy(0)而不是new ListNode(0)。栈上对象自己会释放不用你操心delete用new还要记得释放多一层风险。2.4 画蛇添足需不需要new节点我见过不少初学者在合并循环里这样写tail-next new ListNode(l1-val);潜意识里可能觉得“合并成一个新链表就要创建新节点”。但这个理解是有问题的。题目只要求合并成一条有序链表没有规定“必须由新节点组成”。链表本来就是一个节点通过next串起来的结构直接把原有节点重排更符合链表的本质也更高效。每次new一个节点既多花时间又多占内存还引入一个很麻烦的问题这些new出来的节点在测试结束后谁来释放在在线评测系统里进程结束操作系统会回收内存一般看不到问题但当你在本地写完整测试程序或进入真实C工程环境内存泄漏就会被检测工具毫不留情地标出来。那么什么时候才真的需要new如果题目明确要求“不能修改原链表”或者要求“返回一个全新的链表、与输入链表完全独立”那就必须复制节点。很多题库里的标准场景其实允许复用原节点因为合并本身就是一个“重新连接指针”的操作并不需要复制数据。所以写代码之前先问清楚自己我现在new这个节点是为了满足功能需求还是只是习惯性代码模板如果答案是后者删掉它直接复用原节点更简洁。3. 标准解法背后的关键决策迭代与递归3.1 迭代法虚拟头节点dummy的完整实现先给一份标准、可靠、也很容易被接受的迭代解法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) {} }; ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode dummy(0); ListNode* tail dummy; while (l1 l2) { if (l1-val l2-val) { tail-next l1; l1 l1-next; } else { tail-next l2; l2 l2-next; } tail tail-next; } tail-next l1 ? l1 : l2; return dummy.next; }逐行拆开看。dummy(0)在栈上创建了一个值为0的虚拟节点它不参与最终链表内容只是作为合并起点的占位。tail指向dummy表示当前已合并链表的末尾。循环条件是l1 l2保证两个候选节点都存在才进行比较。比较后把较小节点挂到tail-next上同时让对应链表的头指针向后移动一位。tail tail-next把“末尾指针”移动到新接上的节点。循环结束后tail-next l1 ? l1 : l2把剩余段落整体接上最后返回dummy.next作为真正的链表头。有的人会纠结比较符号用还是。两边的链表自身都有序所以遇到相等节点时选哪一边都不影响全局升序。但如果希望逻辑稳定、便于记忆用并且让l1优先出场更干净。这个写法也方便你后续在处理需要稳定性的场景时直接迁移。迭代法的空间复杂度是O(1)只用了几个指针时间复杂度是O(nm)因为每个节点最多被访问一次。这里有一个容易写错的细节tail tail-next这行必须放在选择完节点之后。如果你先移动tail再执行tail-next l1等于把一个节点接到自己后面链表连接关系直接错乱。这种顺序错误很难通过打印值发现因为打印出来可能每个数字都对但节点之间的next已经完全不对了。3.2 递归法终止条件与递归关系递归解法同样经典而且对理解递归建模很有帮助ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if (!l1) return l2; if (!l2) return l1; if (l1-val l2-val) { l1-next mergeTwoLists(l1-next, l2); return l1; } else { l2-next mergeTwoLists(l1, l2-next); return l2; } }递归的模型是merge(l1, l2)的结果一定是两个头节点中较小的那个作为新链表的头它的next则交给规模更小的子问题——merge(较小头的next, 另一个链表头)。每调用一次规模至少减少一个节点最终触达基础情形l1为空直接返回l2l2为空直接返回l1。这里有一个非常容易写错的地方只写一个终止条件或者把终止条件写成if (l1 nullptr l2 nullptr) return nullptr。后者虽然也能得到正确结果但它没有利用“一个链表为空时另一个链表本身就是有序的”这个事实导致非空链表也被递归一层层拆进去白白增加调用开销还更容易出错。两个终止条件合并成一句话是正确的做法。递归解法的空间复杂度是O(nm)。最坏情况下两条链表交替取值递归深度接近nm每一层都是一次函数调用。链表一长栈压力非常明显。比如一百万个节点的链表迭代法稳稳跑完递归很可能直接爆栈。所以工程代码里更推荐迭代式写法但刷题或面试时能写出递归版本可以展示你对递归建模的熟练度。面试官一般先让你写迭代再追问“能不能用递归”两者都能讲清楚是非常加分的。3.3 复杂度与正确性为什么一定是O(nm)先看时间。无论是迭代还是递归每次操作都只会把一个节点固定放到结果链表中节点总数是nm因此操作次数上限就是nm不可能重复遍历某个节点因为没有一条链表的指针会回头。再看正确性。很多人“试了几个用例都通过”就认为代码一定没问题但对这种基础题更好的做法是理解它为什么一定对。可以用循环不变量来解释每次迭代开始前tail之前的所有节点已经构成一条升序链表它们分别来自l1和l2的前缀。接下来比较两个候选节点的值选择较小者接上。由于l1和l2各自有序选出的节点一定不小于tail当前值所以新链表继续保持升序。循环结束时某条链表为空剩余的另一条链表里所有节点都大于等于已排序链表的最大值整段接上依然有序。这个证明过程比代码本身更有价值。能把“为什么对”讲清楚面试时即使要求加个条件或换个场景你也能迅速推理出改造方向。写算法题时养成“同时准备正确性证明”的习惯是通往更难题目的捷径。4. 调试与排查如何快速定位链表问题4.1 三板斧打印、断点、单步链表题出错时的第一反应不应该是“盯着代码看”而是用工具直接看链表状态。最朴素的打印法在任何环境都适用ListNode* p dummy.next; int count 0; while (p count 20) { std::cout p-val - ; p p-next; count; } std::cout std::endl;为什么强制限制最多打印20个节点因为一旦链表被接成环while会永远循环下去程序直接卡死。加了计数器后即使有环它也只是打印一定数量的节点后结束你能立刻从输出中看到“值在重复”从而推断出成环。如果你在用带调试器的IDE断点法更直接。在tail-next l1这些赋值语句处打断点观察每次被赋值进去的节点地址。如果发现某个地址在前后两步中被重复引用说明链路里出现了环或者重复指向。单步跟踪尤其适合检查“tail tail-next”的位置你会发现结构是否在正确的地方发生跳转。打印法里有个小经验打印返回值之后再多写一个计数函数数一数返回链表有多少个节点。如果节点数比预期少那就是断尾如果打印过程中出现重复值那就是成环如果实际节点数与期望一致但顺序不对再去检查比较符号是还是。这三类问题覆盖了这道题几乎全部的错误形态。4.2 边界用例自测清单刷题不能只靠样例过一遍就完事。我建议把边界用例整理成一张表提交前逐行核对场景输入期望输出两表皆空l1nullptr, l2nullptrnullptr一边为空l1nullptr, l2[1,2,3][1,2,3]都是单节点[1], [2][1,2]长度差异大[1,3,5,7,9], [2,4,6][1,2,3,4,5,6,7,9]所有值相等[1,1,1], [1,1][1,1,1,1,1]一条完全小于另一条[1,2,3], [4,5,6][1,2,3,4,5,6]这些用例各有针对性。“两表皆空”和“一边为空”专门检测空指针处理“长度差异大”专门抓断尾“所有值相等”帮你验证比较符号和稳定性“一条完全小于另一条”则能确认循环结束后另一条链表能完整接上。为了在本地方便构造这些用例可以写一个把vector转成链表的辅助函数ListNode* buildList(const std::vectorint vals) { ListNode dummy(0); ListNode* tail dummy; for (int v : vals) { tail-next new ListNode(v); tail tail-next; } return dummy.next; }有了这个函数你可以手动构造任意链表把上面表格里的场景一个个跑出来。测试时输入输出写在明处错误定位就快了很多。4.3 写一个toVector辅助函数做回归验证除了构造链表我强烈建议再写一个toVector函数把链表变成vector后直接对比std::vectorint toVector(ListNode* head) { std::vectorint res; int count 0; while (head count 100) { res.push_back(head-val); head head-next; count; } return res; }然后可以这样使用assert(toVector(mergeTwoLists(buildList({1,3,5}), buildList({2,4,6}))) std::vectorint({1,2,3,4,5,6}));这个做法比肉眼盯输出可靠得多。把期望结果写成断言跑一遍不通过就立刻知道哪个用例挂了。为什么给toVector也加count限制因为你不知道返回链表是否有环加个长度上限能防止无限循环。测试完如果需要手动释放内存再写一个freeListvoid freeList(ListNode* head) { while (head) { ListNode* next head-next; delete head; head next; } }这套“构造—合并—转vector—断言—释放”的流程不只是给这道题用的。它适合所有链表类题目以后刷反转链表、删除倒数第N个节点、找中点之类的题都可以直接复用。5. 从这道题延伸出去的经验5.1 内存管理new出来的节点谁来释放很多刷链表题的人长期以来没有认真对待内存释放原因是在在线评测系统中进程一旦结束所有堆内存由操作系统回收内存泄漏不会被报出来。但这是“平台代码”不是“工程代码”。在真实的C程序里内存泄漏会让程序随着运行时间变长逐渐膨胀最后被后台监控无情地杀掉。回到这道题。如果合并过程完全复用原链表节点那么你要释放的是两条原始链表如果合并过程用了new创建新节点那么你要释放的是结果链表。两种方案的内存归属完全不同别混在一起。比较容易踩的细节是如果用了ListNode* dummy new ListNode(0)合并结束后dummy节点本身并不在结果链表里delete dummy也不会误伤结果链表的第一个节点你可以安全地先取出dummy-next再delete dummy。如果用的是栈上对象ListNode dummy(0)完全不需要这一步。我还见过一种情况题目要求不修改原链表于是有人复制节点创建新链表然后测试结束只释放了新链表把原链表忘了。两条都来自buildList都通过new创建那就都要释放。总之原则只有一条谁new的谁负责delete。写测试代码时把每个new都对应到delete链表题的正确性才算闭环。5.2 由合并两个链表延伸的经典题合并两个有序链表不只是孤立的easy题它是一系列链表问题的地基。最直接的延伸是链表版的归并排序把链表从中间拆成两半分别排序再调用这里的两链表合并过程。掌握了“找中点”“拆链表”“合并”三个子问题归并排序链表版就是拼积木。再往外延伸是合并K个有序链表。暴力做法是两两合并虽然代码简单但总复杂度是O(kn)当K很大时不够高效。进阶做法是用优先队列维护K个头节点每次取最小、补新头整体复杂度变成O(nlog k)。这个进阶解法建立在你清楚“单次合并最小节点怎么选”的基础上。其实所有链表题都共享同一套思维方式明确每个指针的语义维护正确的循环不变量再落笔写代码。很多人一上来就写while把变量名混在一起最后只能全删重来。如果你能在动手前先用注释写出三个信息——dummy是什么、tail是什么、循环结束时指针状态是什么——代码质量会明显提升。5.3 一些写法上的小习惯我自己的习惯是写链表题时永远先写空指针分支再写主逻辑。这道题里就是先写if (!l1) return l2; if (!l2) return l1;确保后续主循环里两个指针一定非空。这个习惯养成之后空指针类问题会大幅减少。变量命名也很关键。用dummy、tail、prev、curr这类能表达职责的命名而不是a、b、c。变量名就是你在代码里留下的注释尤其是链表这种高度依赖指针语义的场景好名字能救命。写完代码后我会手动把最小例子在纸上走一遍两个单节点链表一个值是1一个值是2跟着代码一步一步移动指针亲自验证结果为什么是[1,2]。最后分享一个我自己很受用的方法写完代码后用一两句话把整个流程讲给自己听。比如“tail先指向dummy每次把较小的节点接到tail后面然后tail跟着新节点走直到某条链空了把剩下那条整段接上”。如果这段故事能讲得通顺、不卡壳代码基本不会有大的方向性问题。如果讲着讲着发现某个环节说不清楚那这个地方往往就是bug所在。提示对easy题别急着“刷完就走”。把空指针、断尾、返回值这三个错误点真正刻进脑子比连续做十道新题更有价值。以后碰到任何链表合并类问题你会发现自己一眼就能看到危险区在哪里。
阅读完成 · 觉得有帮助？
)` 成为合法代码)
