题目是“习题2.5 两个有序链表序列的合并”光看标题可能觉得不就是个链表合并嘛有什么好讲的。但真正动手写过的人应该知道这道题几乎是所有数据结构教材里链表章节的“标配”题目也是很多人第一次感受到“指针操作原来这么容易翻车”的地方。我见过太多同学上课听懂了一到上机就卡住要么是链表越接越乱要么是处理到最后丢了一截结点。今天这篇我就把这道题彻底拆开从读题、设计思路、两种主流写法到常见坑位全部过一遍代码可以直接抄原理也讲明白希望能帮你真正把它吃透。核心关键词顺手丢出来链表、有序链表、合并。这三个词基本就是这道题的全部家当也是后面所有讨论的出发点。我会围绕它们讲清楚什么叫有序链表、合并的本质是什么、以及为什么这道题值得反复练习。1. 题目到底在考什么读题与思路拆解1.1 先搞清楚题目要求这道题通常的表述是这样的已知两个有序链表A和B它们的元素按非递减顺序排列要求将A和B合并成一个新的有序链表C合并后元素仍然按非递减排列。注意几个关键限定词。首先是“有序链表”意味着两个链表各自内部是有序的如果拿到的是乱序链表那就不是合并问题了得先排序。其次是“非递减”不是严格递增也就是说链表中允许出现相同数值比如1-2-2-3这种也算有序。合并的时候相同元素如何处理取决于题目要求是“去重合并”还是“简单合并”大部分教材题默认保留重复值即1-2和1-2-3合并后得到1-1-2-2-3而不是去重后的1-2-3。这一点我建议拿到题目先确认清楚不然写完了发现结果不对很麻烦。这道题考察的知识点表面上是“链表遍历”和“链表插入”但往深了说它其实在考察三个能力能否理解链表不连续存储的特性以及指针在结点间移动的逻辑能否在有序序列上高效地利用顺序性而不是无脑地把两个链表塞进数组再排序能否正确处理边界情况比如空链表、长度不等、连续重复值等换句话说这道题虽然代码量不大但它是一座微型“炼钢炉”能把链表操作的基本功都检验一遍。1.2 为什么“合并”这类题值得反复练很多同学觉得链表题难难在“抽象”。数组里你要访问第i个元素直接arr[i]就完事了逻辑和人类的直觉一致。但链表不同你只能从头结点开始通过next指针一个结点一个结点地“跳”每一步操作都要自己维护好当前的“位置感”。一旦指针指错了很可能不是编译错误而是运行到一半程序直接崩溃或者链表被接成了一个环死循环卡死。而“合并”这个操作正好包含了几种最典型的链表操作遍历沿着next走、比较两个链表当前结点的值大小、插入把选中的结点接到结果链表的尾部或指定位置、以及边界处理某个链表先走完时直接接上剩下的部分。练会了这一道题等于练会了链表操作的大部分基本功后面再刷“链表反转”、“链表排序”就不会那么慌了。另外这道题还有一个很关键的变体能否原地合并也就是不申请额外的新结点只通过改变指针指向来完成合并。如果能做到这一点空间复杂度可以从O(nm)降到O(1)这也是面试中经常追问的加分点。1.3 两条主路线新建链表与原地复用我习惯把这类题目的解法分成两条路线写代码之前先想清楚走哪条能少踩很多坑。第一条路线是“新建链表法”。定义一个新的头结点或指向NULL的头指针然后同时遍历A和B每次比较两个当前结点的大小把较小的那个从原链表“摘”下来接到新链表尾部。这个思路直观代码好写但缺点是需要额外空间来存放新链表。第二条路线是“原地合并法”也叫原地归并。不新建结点而是从A和B的头结点中挑一个作为合并后的头让它的next继续去合并剩余部分。这样做空间复杂度是常数级别的代码反而更精妙一点也更体现功力。你可能会想这两种写法本质上都是“比较后链接”代码似乎差不多区别在哪里呢区别在于是否允许修改原链表。新建法可以保持原链表不动原地法则会直接把原链表A和B“拆掉重组”。实际应用场景里这个区别很重要如果原链表还要保留就不能用原地法。下面两章我分别给出这两种路线的完整代码和详细分析你按照自己的需求选用。2. 基本功循环迭代合并的完整实现2.1 带头结点写法最稳的答案先给出一个我推荐初学者使用的写法利用“带头结点”的链表设计可以省去大量空指针特判。所谓带头结点就是链表的第一个结点是一个不存数据的哑结点真正的内容从第二个结点开始。这样做的最大好处是即使在新链表为空时也有一个确定的结点可以让你把新结点“挂”上去不用单独判断头指针是否为NULL。下面是完整代码使用C语言实现假设链表结点定义如下#include stdio.h #include stdlib.h typedef struct LNode { int data; struct LNode *next; } LNode, *LinkList; // 合并两个非递减有序链表返回新的带头结点的链表 LinkList MergeList(LinkList A, LinkList B) { // C是结果链表这里C本身带头结点单独用一个结点来避免NULL判断 LinkList C (LinkList)malloc(sizeof(LNode)); LNode *tail C; // tail始终指向结果链表的最后一个结点 LNode *pa A-next; // 跳过A的头结点指向第一个数据结点 LNode *pb B-next; // 跳过B的头结点 while (pa ! NULL pb ! NULL) { if (pa-data pb-data) { tail-next pa; // 把pa接在tail后面 pa pa-next; // pa后移 } else { tail-next pb; pb pb-next; } tail tail-next; // 更新tail } // 把剩下的部分直接接上 if (pa ! NULL) { tail-next pa; } else { tail-next pb; } return C; }核心逻辑其实就一个while循环加一个收尾操作但有几个细节值得反复品。第一tail指针的更新时机。很多人写这种题会忘记更新tail结果每次都是往同一个结点的next上插合并完发现链表只有两个结点其余全部“失踪”。正确做法是每接入一个结点tail就立刻指向这个新接入的结点让下一次插入位置跟着走。第二注意对比边界。while (pa ! NULL pb ! NULL)只要有一个链表遍历完了循环立刻结束。这时候另外一条链表剩下的结点直接整体接到tail后面即可因为剩余部分本身依然有序无需再遍历比较。第三这个写法有一个小聪明的地方是直接在循环里用pa-next更新指针而不是先暂存再更新。由于接入的是原链表的结点我们在改变tail-next之前先保存了pa或pb的next实际上这个顺序在代码里是“先接入、再移动指针”。如果你反过来写比如先把pa-next改了再去取pa-next那么原来的后继就找不到了。这里面的顺序问题一定要想明白。2.2 不带头结点写法看清指针的边界有些教材或实验平台不给头结点链表直接用头指针指向第一个数据结点。这时合并就要多费点心思。先看代码// 不带头结点合并后返回新链表的头指针 LinkList MergeListNoHead(LinkList A, LinkList B) { // 两个空链表的情况 if (A NULL) return B; if (B NULL) return A; LinkList C NULL; // 结果链表的头指针 LinkList tail NULL; // 先确定头结点谁小谁当头 if (A-data B-data) { C A; A A-next; } else { C B; B B-next; } tail C; while (A ! NULL B ! NULL) { if (A-data B-data) { tail-next A; A A-next; } else { tail-next B; B B-next; } tail tail-next; } if (A ! NULL) tail-next A; else tail-next B; return C; }与带头结点版本最大的区别在于新链表的头指针C需要单独处理。因为链表为空时头指针必须时NULL插入第一个结点后头指针要指向它。如果你不单独处理第一次插入后面统一用tail-next去接那第一个结点就永远丢失了。我的习惯是先把头定好再进入循环。也就是先比较A和B的第一个结点谁小谁作为结果链表的头然后tail指向这个头后面循环从第二个结点开始比较。这样逻辑清晰也不容易出错。这个“确定头结点”的思想其实也适用于很多需要动态生成链表的场景。比如从数组构建链表时第一个元素也要特殊处理除非你用带头结点方式。如果你把这条思路记牢了不带头结点就再也不会卡在“第一个结点怎么挂”这种问题上。2.3 时间与空间复杂度分析这道题的时间复杂度非常直观最坏情况下两个链表的所有结点都要被比较一遍所以整体是O(mn)m和n分别是两个链表的长度。空间复杂度则取决于写法如果新建链表且每个结点都新malloc空间复杂度是O(mn)如果复用原有结点只改变指针指向额外空间复杂度是O(1)这里我想强调一个容易被忽略的点“新建链表”不一定要新malloc结点。你可以把A、B的结点取下来重新搭一个链表C这本质上只花了O(1)的额外空间只是改变了链表结点的归属。严格说这不是“新建”而是“重组”。如果面试官问“能不能O(1)空间实现”你要理解他问的是能否不新开结点、只改指针那答案就是上面那两种写法都可以算O(1)只要你没有为结果链表重新分配结点。另外如果你用的是普通的迭代写法时间复杂度和递归写法一致区别只在于递归会消耗系统栈空间深度为O(mn)而迭代则没有这个问题。下文讲递归时我会再详细展开。3. 少写代码的递归解法3.1 递归思路把大问题拆成小问题递归解法在思路上更接近数学归纳法。假设函数MergeList已经能合并两个有序链表那么对于当前的两个链表A和B只需要比较它们的第一个结点谁更小谁就是合并后链表的头然后让这个头的next指向“剩下的结点继续合并的结果”。用一句话概括就是head min(A, B)head-next MergeList(head-next, 另一个链表)。这是一个经典的“分治式”递归模板。我见过很多同学写递归时纠结“返回值怎么传”其实诀窍在于让返回值永远是“当前这一层合并完后的头指针”上一层通过next把它接住。3.2 递归代码实现LinkList MergeRecursive(LinkList A, LinkList B) { if (A NULL) return B; if (B NULL) return A; LinkList head NULL; if (A-data B-data) { head A; head-next MergeRecursive(A-next, B); } else { head B; head-next MergeRecursive(A, B-next); } return head; }注意这里的输入链表是不带头结点的输出也是不带头结点的。如果是带头结点你需要先把头结点摘掉再递归最后把结果挂在另一个新头结点后面。这段代码只有五行核心逻辑但背后有几点必须想清楚递归的终止条件是两个链表中有一个为空。此时剩下的链表已经有序直接返回即可。当A-data B-data时A的当前结点胜出成为新链表的头后续部分由A的下一个结点和B整体递归合并而成。每次递归只处理“当前最小结点”剩下的交给下一层。这是理解这段代码最关键的视角。3.3 递归的优缺点面试常问递归写法最直观的优点就是代码简洁而且逻辑和人的思维方式高度吻合写起来不容易漏边界。LeetCode第21题“合并两个有序链表”的官方题解里就包含这种写法很多教材也把它列为标准解之一。缺点是它使用系统调用栈递归深度与链表长度成正比。假设链表有一万个结点递归调用就会有一万层在工程上可能导致栈溢出。因此实际开发里我更倾向于使用迭代法但面试时如果被问到写出递归解法往往会让面试官觉得你思路清晰因为它天然展示了“把问题分解为子问题”的能力。还有一个小缺点容易被忽略递归解法会逐层返回头指针因此不能做到完全的尾递归优化部分编译器会将其优化为循环但不是所有编译器都这么做。稳妥起见如果你担心性能就用迭代法。4. 经典教材“AB集合”场景合并与去重扩展4.1 严蔚敏教材中的那道经典题如果你用的是国内高校非常普及的《数据结构C语言版》严蔚敏的教材那么这道“习题2.5”大概率是这样描述的已知两个链表A和B分别表示两个集合其元素递增有序请设计一个算法求出A和B的交集、并集或差集。其中“合并”相关的一种问法是求两个集合的并集并要求结果链表仍然递增有序。这里有一个本质区别需要注意集合不允许重复元素。也就是说如果题目说“A和B分别表示两个集合”那么合并时要去重。比如A {1, 2, 3}, B {2, 3, 4}合并求并集的结果应该是1-2-3-4而不是1-2-2-3-3-4。所以当你看到“集合”二字时合并的规则立刻从“直接归并”变成了“归并去重”。这不仅是一个边界条件的变化更是一个逻辑层面的变化当A和B当前结点的值相等时结果链表只能保留一个另一个需要释放并且两个链表都要向后移动。下面是带去重功能的合并代码LinkList MergeSet(LinkList A, LinkList B) { LinkList C (LinkList)malloc(sizeof(LNode)); C-next NULL; LNode *tail C; LNode *pa A-next; LNode *pb B-next; while (pa ! NULL pb ! NULL) { if (pa-data pb-data) { tail-next pa; tail pa; pa pa-next; } else if (pa-data pb-data) { tail-next pb; tail pb; pb pb-next; } else { // 相等只保留一个释放另一个 tail-next pa; tail pa; pa pa-next; LNode *tmp pb; pb pb-next; free(tmp); } } // 剩余结点仍然需要去重吗 // 因为每条链表内部已经有序且无重复剩余部分直接接上即可 if (pa ! NULL) tail-next pa; else tail-next pb; return C; }注意我刚才在注释里写了一句“剩余部分直接接上即可”。这依赖一个前提原链表A和B自身内部没有重复元素因为它们是“集合”的表示。如果原链表内部自身就允许重复比如不是集合而是多重集合那么剩余部分也需要逐一检查去重代码会比这个复杂很多。这也是我觉得必须扣题眼的原因——你先根据题目描述判断清楚它到底是简单合并还是集合合并再去写代码。4.2 不带头结点时的处理细节如果你在实验题里遇到不带头结点的“集合合并”处理方式类似但要额外注意释放结点时不要破坏指针顺序。比如上面代码中pa-data pb-data的分支里我先把tail-next pa接好再让pa后移最后再释放pb。这个释放顺序是有讲究的如果先把pb释放了但又不知道它是否还被哪里引用可能引发野指针问题。这里因为pb已经不再被原链表需要释放安全但必须先保存pb-next我代码里是先让pb pb-next然后用tmp保存旧的pb再free顺序等价。很多同学写链表代码最容易翻车的地方就是“释放结点”和“移动指针”的顺序搞反。记住一条通用规则先保存后继再修改指针或释放当前结点。4.3 涉及求交集/差集时的变形既然热词里出现了“合并去重”我再顺手讲一下如果题目让你求交集或差集应该怎么改。求交集时只有当pa和pb的data相等才把该结点接入结果链表其余情况都只移动指针且释放较小时或不释放视题目要求。求差集时即A-B只保留属于A但不属于B的元素那么当pa-data pb-data时pa保留并接入结果链表两者相等时两个都向后移动并释放或者只移动pa-data pb-data时pb后移。这三个操作分支思路完全一致代码是在合并框架上做条件变化而已。我建议你把“合并去重”“交集”“差集”这三个版本都亲手写一遍。写完之后你会发现它们本质上是同一套模板熟练之后对链表操作的理解会上一个台阶。5. 常见错误与排查技巧实录5.1 指针丢失这是链表题里最经典的问题。什么叫指针丢失比如你想把pa接到tail后面写了tail-next pa之后又写了pa pa-next这时如果pa已经是被接入的那一个结点而你没有提前保存pa-next下一步就只能拿到NULL或错误地址。因为在接入操作里tail-next pa已经把pa的next也改变了不一定取决于pa原本的next是否被覆盖。实际上当你执行tail-next pa时只改了tail-next没有改pa-next所以如果代码顺序是“先papa-next再tail-nextpa”反而会丢。正确的顺序一定是先保存/移动指针再接链。再提供一套我觉得最不容易出错的“接结点四步法”用临时指针tmp保存将要接入结点的后继LNode *next pa-next;把结点接入tail-next pa;更新tailtail pa;移动原链表指针pa next;这套流程虽然多一个临时变量但每一步都清晰尤其适合刚学链表的同学。写熟练之后你再逐步简写也不会出错。5.2 空链表处理遗漏我见过不少同学写完代码后拿两个非空链表测试没问题但一提交就报段错误debug半天才发现是没处理空链表。如果A或B一开始就是空链表你的代码如果没有判断if (A NULL) return B;这类逻辑就会直接访问A-data或A-next导致对NULL解引用。NullPointerException虽然在C里叫“段错误”但本质一模一样。建议任何链表操作题都先想清楚三件事输入的链表能否为空操作过程中链表是否会变空函数应该返回什么把这三个问题在纸上画一画很多bug都能提前避免。5.3 成环问题链表合并时如果操作不当容易把结果链表接成一个环导致遍历时死循环。典型的场景是你把pa接到tail后面以后忘记让tail-next最终指向NULL然后仍然继续循环某些情况下会把之前已经接入的结点再接入一次形成环。排查环的最笨但有效的方法是拿一组很小的数据比如链表A {1, 2}B {3, 4}在纸上手动模拟一遍每次更新tail和当前指针都画出来。如果你画的图和代码行为一致但还是有环说明是逻辑问题如果和代码行为不一致那就是代码和思路脱节了。另一个技巧是在调试时临时在循环末尾打印tail-data和tail-next-data如果出现重复大概率是成环了。5.4 一个真实debug案例我自己当年写这道题时踩过的一个坑是合并完以后直接返回了C头指针但C头结点没分配内存。我用的带头结点写法定义了LinkList C;就想直接返回C结果运行时一看C指向一个随机地址整个链表直接炸掉。后来就养成了习惯带头结点时必须malloc一个真正的头结点即使它不存数据也必须占一个合法地址。还有一次是笔试时用递归写忘了处理两个链表都是空的情况。其实如果A和B都为空递归版本会直接返回NULL这段逻辑本身没问题但当时我加了一句if (A NULL B NULL) return NULL;虽然后面证明这是冗余代码但面试官看到后以为我不清楚递归终止条件还追问了我几句。这件事给我的启发是代码不是越长越好冗余逻辑反而会暴露对概念理解的不到位。6. 从这道题延伸开去并归排序、LeetCode与工程应用6.1 和归并排序的关系仔细看这道题的合并逻辑你有没有觉得它和“归并排序”有种似曾相识的感觉归并排序的核心步骤之一就是把两个已经有序的子序列合并成一个有序序列。链表的归并排序恰恰就是依赖这个“合并有序链表”的函数的。如果你想学习链表的归并排序这道题就是它的前置技能。当你把两个有序链表的合并写熟后可以试着把数组中的数据一个个用头插法或尾插法构建成链表再写一个递归或迭代的归并排序来对整个链表排序。链表排序和数组排序最大的不同在于不需要额外的O(n)辅助空间去存拷贝只要改变指针就能完成排序这也是工程中链表数据结构的一大优势。6.2 LeetCode 21题与面试考点如果你打算刷LeetCode第21题正是“合并两个有序链表”和这道习题基本同源。LeetCode上的函数签名是ListNode* mergeTwoLists(ListNode* list1, ListNode* list2)输入输出都是不带头结点的链表。你可以把上面“不带头结点”的代码稍作修改提交就能通过。面试时面试官常常会在这个基础上做“连环追问”如果两个链表有环怎么办可以先检测环再合并或者直接说明工程上不允许传入有环链表如果结果要求去重呢这就回到上面讲的集合合并版本如果链表数据是字符型而不是整型呢思路完全一样只是比较规则换成字符比较如果要求合并后是严格递增不允许相等相邻呢相等时只保留一个即可这些变体看上去复杂但只要你理解了“比较两个当前结点取较小者接入结果”这一核心逻辑就都能应对。我建议你先把最基础、最经典的版本写通再逐个攻破变体。6.3 工程应用场景漫谈有人可能会问这种链表合并的题目真的在实际开发中用得上吗说实话现代工程里直接用裸链表的地方不多但也不是没有。比如操作系统内核里的任务队列管理某些内存分配器使用空闲块链表来合并相邻的空闲块区块链的区块打包也可能涉及合并有序交易列表一些缓存系统会使用链表维护LRU顺序合并操作同样会出现在数据合并场景中。更实际一点地说这道题训练的核心能力——两个有序序列的归并——在很多非链表场景中也频繁出现。比如两个有序数组的合并后面可以扩展成归并排序两个有序文件的外排序归并数据库中两个有序索引块的合并甚至是在Excel里做两个有序数据表的合并逻辑本质都是同一套用两个指针分别扫两条序列谁小谁先进结果。所以说不要小看这一道“习题2.5”它背后是一个非常重要的算法范式。7. 写在最后的实操经验讲了这么多我最后分享几条自己实操多年的体会算是给你提前划的重点。第一链表题的调试纸笔永远是最好的工具。我直到现在遇到复杂的指针操作依然会在纸上画出每个结点的地址、data值和next指向。不要觉得画图麻烦等你debug到凌晨三点还找不到指针错误就知道它有多值钱了。尤其是像这道题的tail指针更新稍微一走神画出来的图和代码就会自己“打架”。第二一定要养成写“边界测试”的习惯。两个空链表、一个空一个非空、两个链表长度差很多、两个链表第一个元素就不同、两个链表完全相同、存在大量重复值这六种用例至少要自己手动测一遍。很多同学写完代码拿两组数据一跑就丢到一边结果考试或面试时栽在最简单的空链表上非常可惜。第三要理解“合并”和“拷贝”的区别。这道题的所有解法几乎都是把原来的结点重新串接而不是复制结点的值、创建新结点。理解这一点之后你自然能明白为什么修改链表时要注意释放问题、为什么需要保持原链表的结点完整。如果你在做工程时不想改动原链表那就要真正新建结点并复制数据这叫深拷贝如果只改动指针那是浅拷贝式重组。面试时如果被问“为什么你的代码不会创建新结点”你就可以从空间复杂度O(1)的角度去回答。第四如果你用的是带头结点的链表千万不要忘记给头结点分配空间。这是我在前面也强调过的但即使是我偶尔也会因为切换到不带头结点的代码模板而重新犯这个错。建议你平时练习时就固定一个习惯要么全用带头结点要么全用不带头结点不要在同一个程序里混用否则很容易弄混头指针和第一个数据结点的概念。最后再说一个小技巧很多同学以为“两个有序链表合并”必须同时遍历到两个链表都为空才算完其实完全没必要。因为只要有一个链表走完了剩下的那条链表直接整体接上就可以了。这个“提前退出”的优化我称之为“归并收尾用甩接”代码简洁且不会出错也是面试官期待看到的优化点之一。这道题我前前后后在不同场合写了不下几十遍每次写都有新体会。希望你也能把它练成肌肉记忆一样的基本功后续遇到更复杂的链表题时会感谢自己今天花了这一小时把它彻底搞明白。