这道题我前前后后写了几十遍自己当学生的时候写过带师弟师妹的时候也带他们写过面试候选人的时候还拿它当过考题。它看起来简单无非就是把两条已经排好序的链表串成一条更长的有序链表但真能一次写对的人说实话不多。这道题在《数据结构》课程里出现的频率极高严蔚敏教材配套练习、PTA上的02-线性结构1、各种期末卷子、考研机试甚至一线互联网公司的算法面试都是同一个套路。它考的不是你会不会背某个算法而是你对线性结构最本质的理解怎么用指针去操作节点怎么处理边界条件怎么在不用额外数组空间的情况下完成一次线性扫描。这篇文章就把这道题彻底讲透从题目本身的考察意图到带哨兵节点的链表设计再到完整可运行的C语言代码、测试用例设计和各类翻车现场全部过一遍。不管你是在准备数据结构期末考试、考研机试还是面试前临时抱佛脚这篇都值得认真看。1. 题目拆解与设计意图这题到底在考什么1.1 先看清楚输入输出契约题目描述一般不长核心要求是给定两条已经按非递减顺序排列的链表把它们合并成一条新的链表合并后的链表也必须是非递减有序的。注意是“非递减”不是“严格递增”这意味着数据里完全可能出现相等的元素比如1 - 3 - 5和1 - 2 - 6合并后应该是1 - 1 - 2 - 3 - 5 - 6。很多人一上来直接写“两个链表比较大小小的先接到结果链上”逻辑上没错但有一个隐藏问题两条链里都有1这个1到底先取L1的还是L2的从题目角度讲两种情况都合法不影响结果是否有序。但如果你在处理时用而不是当两个值相等时你可能就把某个链表剩下的节点全部兜底接上了后续元素的顺序就会变得不可控虽然仍然是有序的但不符合我们通常对“稳定合并”的预期。这里建议统一用先取第一个链表的相等元素逻辑更干净写起来也顺手。输入输出格式一般是用带头结点的单链表。也就是说L1、L2本身是一个空的头节点L1-Next才指向第一个实际元素。合并函数接收这两个头指针返回合并后链表的头指针。这个“头结点”设计非常关键后面会专门讲。1.2 为什么这题能进教材因为它卡住了一堆指针细节如果把两条有序链表想象成两摞已经排好的卡牌合并的事情本质是把两摞卡牌各抽出一张比较大小小的放到新的一堆里然后被抽走的那一摞指针往后移动一个位置。这个过程用数组也能做但前提是需要额外申请一个大小等于两数组长度之和的数组还要把元素搬过去。用链表做只需要改指针让结果链表的尾节点不断指向“当前比较中较小元素的节点”整个过程中不需要申请新节点也不需要移动任何数据。所以这题真正隐蔽的考点是你是否清楚“尾插法”建立链表的过程以及为什么合并时也必须记录结果链表的尾节点你是否对“空链表”“任意一个链表为空”这类边界情况有警觉你是否能区分“把节点接到结果链上”和“把节点值拷贝到新节点里再把新节点接上去”两种做法你是否知道最后循环结束时某个链表中可能还剩一串节点这个“收尾”操作最容易被漏掉。很多同学栽就栽在最后一步循环里把两条链表比较完了结果tail-Next还指着空白折腾一场。这种错误不是逻辑不懂是对指针操作不够熟练用这道题来练这种熟练度再合适不过。2. 核心实现策略带头结点与哨兵位的巧劲2.1 先理解单链表的基本形态C语言里定义单链表节点最常见的方式是typedef struct LNode { int Data; struct LNode *Next; } LNode, *List;这里的typedef是把struct LNode重命名为LNode同时把struct LNode *重命名为List。后面写代码时List L就可以直接声明一个链表头指针不用再写繁琐的struct LNode *L。每个节点有两个字段Data存放数据Next存放下一个节点的地址。整条链表的“形状”是靠指针串联起来的链表的结束标志是Next NULL。这里有一个初学者很容易搞混的点List本身是一个指针类型它指向的是LNode。那当我们说“定义一个链表List L”时这个L到底表示头结点还是第一个数据节点在没有特别说明的情况下我们的约定是L是一个指向头结点的指针头结点本身不存数据或者Data字段闲置L-Next才指向第一个真正的数据节点。后面代码里所有的操作都遵守这个约定。2.2 为什么合并时要创建一个哨兵头节点合并函数的经典写法是List Merge(List L1, List L2) { List head (List)malloc(sizeof(LNode)); List tail head; List p L1-Next; List q L2-Next; while (p q) { if (p-Data q-Data) { tail-Next p; tail p; p p-Next; } else { tail-Next q; tail q; q q-Next; } } tail-Next p ? p : q; return head; }malloc出来的head就是哨兵节点也常被称作虚拟头节点。这个节点本身不携带有效数据它的作用只有一个让tail在初始状态有一个可以指向的地址。否则如果结果链表刚开始是空的你就需要额外判断“当前结果链表是否为空”如果为空就直接让结果头指针指向第一个节点如果不为空就接在尾部。这种分支判断不仅啰嗦还容易漏掉某个分支。用哨兵节点的好处是无论结果链表现在有没有元素tail-Next都一定可以被赋值尾插法的逻辑从头到尾保持统一。2.3 尾插法的指针更新顺序不能乱看上面代码里的这一段tail-Next p; tail p; p p-Next;三行代码顺序不能颠倒。如果先执行p p-Next那么p原来的地址就丢了你再也找不到这个节点了也就没法把它接到结果链上。如果先执行tail p再执行tail-Next p那等于把tail指向了p然后又把自己的Next指向了自己形成环。这种“先接、再移、再回”的节奏是所有链表插入操作的通用模式。你可以记成三点操作新节点的Next指向当前节点的Next当前节点的Next指向新节点最后移动工作指针。只不过在合并场景里被接入的节点不是新创建的而是从原链表“拆”过来的所以要额外把原链表的工作指针往后推进一位。很多同学刚开始写链表代码时会觉得别扭因为普通顺序表只需要改变数组下标而链表里每做一个动作都要考虑指针指向谁、原来的引用是否还保留。这恰恰是最值得练的地方。2.4 收尾操作的精髓一次拼接节省到底循环结束后p和q至少有一个是NULL也可能两个都是NULL。很多人这里会写while (p) { tail-Next p; tail p; p p-Next; } while (q) { tail-Next q; tail q; q q-Next; }这样写当然没错但没必要。因为剩下的部分本身就是一条有序链表你只需要把整条剩余链接上去就行了tail-Next p ? p : q;这一句直接搞定。如果p非空就接p否则接q。如果两个都为空tail-Next NULL也成立。这个操作把循环从最坏 O(mn) 降到了 O(1)也是代码简洁性的体现。到这里你应该能感受到这道题的核心思想它不是在考你会不会排序而是考你会不会用“一次线性扫描 指针拼接”实现两个有序序列的归并。归并思想在后续的归并排序里也会出现是数据结构里最基础也最核心的套路之一。3. 完整可运行实现从读入链表到输出结果3.1 读入链表的函数合并之前需要先构造两条链表。在PTA这类评测平台上输入一般是这样每两行描述一条链表第一行是节点个数n第二行是n个整数。比如3 1 3 5 3 1 2 6读入并构造带头结点链表的方法是标准的尾插法List ReadList() { int n; scanf(%d, n); List head (List)malloc(sizeof(LNode)); head-Next NULL; List tail head; for (int i 0; i n; i) { int x; scanf(%d, x); List node (List)malloc(sizeof(LNode)); node-Data x; node-Next NULL; tail-Next node; tail node; } return head; }这个函数的核心就是每读一个数就新建一个节点尾指针tail始终指向链表的最后一个节点新节点插到tail后面然后tail移到新节点上。3.2 打印链表的函数打印也很简单从head-Next开始遍历到NULL每个元素之间用一个空格隔开注意最后一个元素后面不要输出多余空格避免格式错误void PrintList(List L) { int first 1; List p L-Next; while (p) { if (!first) { printf( ); } printf(%d, p-Data); first 0; p p-Next; } printf(\n); }3.3 主函数与合并调用主函数把整个流程串起来读入两条链表调用Merge打印结果最后释放内存。int main() { List L1 ReadList(); List L2 ReadList(); List L3 Merge(L1, L2); PrintList(L3); return 0; }注意Merge函数返回的是带头结点的链表头指针所以PrintList接收它之后直接从L3-Next开始打印即可。3.4 测试用例设计把边界都测一遍光能跑通样例还不够我强烈建议你自己多设计几组边界用例拿不准的时候就全部跑一遍。用例输入预期输出说明基本用例L1: 1 3 5L2: 2 4 61 2 3 4 5 6两条链表长度相等元素交替包含相等元素L1: 1 2 3L2: 1 2 31 1 2 2 3 3相等元素都要保留顺序无所谓一条全大于另一条L1: 10 20L2: 1 2 31 2 3 10 20一个链表从头到尾都比对方小一条为空L1: (空)L2: 5 6 75 6 7空链表边界两条都为空L1: (空)L2: (空)什么都不输出空链表边界长度差巨大L1: 1L2: 0 2 3 4 5 60 1 2 3 4 5 6循环结束后剩余节点拼接必须正确所有元素都相等L1: 1 1 1L2: 1 1 11 1 1 1 1 1比较符号与稳定性的验证每一条用例都值得亲手跑一遍尤其是“一条为空”和“两条都为空”两种情况。空链表是初学者的重灾区因为平时练习时给的样例大多都有数据一遇到空链表函数里某个地方就会直接崩溃或者返回错误结果。3.5 关于是否释放原链表题目通常不要求释放原链表评测系统评测完就回收内存了所以不写释放函数也不会判错。但作为一个合格的C语言学习者我在本地练习时会把释放函数也写出来这不影响题目得分但对理解链表遍历和节点删除过程是有帮助的void FreeList(List L) { List p L; while (p) { List tmp p; p p-Next; free(tmp); } }注意这个释放逻辑先保存当前节点地址再让指针后移然后释放保存的地址。顺序不能反过来否则p变成野指针后面的p p-Next就会出错。4. 常见问题与排查技巧实录4.1 最常见的段错误空指针解引用很多同学第一次写完一跑就报Segmentation Fault。段错误九成以上是“对NULL指针进行了解引用”。举个例子如果p指向一个空节点你直接访问p-Data系统就会崩溃。但这道题里还有一个不太容易察觉的段错误来源tail-Next p ? p : q;如果p和q都是NULL那tail-Next被赋值为NULL没问题。但如果你在这之前使用了tail而tail一开始没有初始化成head或者更常见的是合并函数里在进行while (p q)之前没有给tail赋初始值那么第一次进入循环时tail可能是野指针访问tail-Next就炸了。排查方法很简单在可疑函数前后用printf打印p、q、tail的地址看到底哪一步开始变成0x0的。我调试链表代码时特别依赖这种“地址打印法”它能直观地告诉你是哪个指针断的。4.2 结果链表只剩一个元素这种情况通常是循环写的顺序错了导致后面的节点不断覆盖前面的节点。举个例子如果循环里写成tail-Next p; p p-Next; tail tail-Next;看起来好像也对但注意tail tail-Next后tail指向的是刚刚接入的节点此时如果下一次循环又执行tail-Next p那新节点是接到了刚接入节点的后面这个逻辑其实是对的。真正的问题是如果你在tail-Next p之后不小心把p当作tail来用或者没有在每次循环中更新 tail就会出现“所有新节点都挂到头节点后面”的情况打印出来自然只剩最后一个接入的节点。这类问题的本质是尾指针没有跟随链表的增长而更新。排查时只需要在循环结束、PrintList之前打印head-Next、head-Next-Next、head-Next-Next-Next看看链表是不是真的串起来了。4.3 输出顺序不对是先取L1还是先取L2的锅比较逻辑里用会导致相等元素的顺序取决于哪个链表先被取完但整体仍然有序所以一般不会产生“乱序”的视觉效果。真正导致输出乱序的常见原因是你在循环里比较的不是p-Data和q-Data而是p和q的地址。如果写成了while (p q)那链表顺序就彻底乱了。这种问题很不显眼因为它不会编译报错p和q作为指针是可以比较地址大小的但这不是我们想要的逻辑。所以遇到输出顺序错乱时先检查比较表达式里有没有漏了-Data。4.4 别偷懒写递归栈溢出风险与效率问题有些同学为了炫技喜欢把这道题的合并写成递归List Merge(List L1, List L2) { if (!L1-Next) return L2; if (!L2-Next) return L1; if (L1-Next-Data L2-Next-Data) { List merged Merge(L1-Next, L2); L1-Next-Next merged; return L1; } else { List merged Merge(L1, L2-Next); L2-Next-Next merged; return L2; } }我承认递归写法代码非常简洁也没用到哨兵头节点直接在原链表上改指针。但你要清楚它的代价递归深度等于合并后链表长度如果链表有十万个节点递归调用栈就会压得很深程序可能直接栈溢出。另外这种写法会修改原链表的结构如果后续还想用L1或L2它们已经被破坏掉了。除非题目明确允许否则我不建议在正式作业或评测环境里这么写。4.5 经验之谈先画图再写代码说了这么多排查方法最朴素的习惯还是那个写链表题之前先在草稿纸上画图。画出两条链表用箭头表示Next然后模拟每一次比较和指针赋值。这个过程看起来笨但它能帮你省下大量调试时间。我在带团队的时候经常说一句话链表题画图半小时写代码十分钟调试五分钟不画图直接写可能调试五十分钟。5. 从这道题延伸开去面试与变体考察5.1 这道题的复杂度时间与空间两手抓合并两个有序链表用上面的迭代写法时间复杂度是 O(mn)因为每轮循环比较或拼接都会让p或q向后移动总共移动 mn 次空间复杂度是 O(1)因为我们没有申请任何额外的存储节点只是创建了一个哨兵头节点。如果你是复制节点值重新建链空间复杂度就会变成 O(mn)虽然也能通过但已经不够优雅。面试官可能会追问为什么不能在 O(m) 或 O(n) 时间内完成答案很简单你至少要把两条链表都遍历一遍才能知道所有元素的相对顺序。如果有任意一个元素没被看到你就无法确定它的位置所以下界就是 O(mn)。能够对复杂度下界有清晰认识的候选人在面试官眼里通常比只会背题的人高一个档次。5.2 变体一合并K个有序链表两个链表会了面试官最常见的变体是“合并K个有序链表”。这里有个很自然的扩展思路两两合并先把第一条和第二条合并再把结果和第三条合并以此类推。这种做法的总时间复杂度是 O(K*N)其中 N 是每个链表的平均长度因为前面合并的结果会越来越长后面的合并都要扫描它。更高效的方案是用优先队列最小堆。先把 K 个链表的第一个节点放进堆里每次从堆中取出最小的节点接到结果链上然后把这个节点的下一个节点放进堆里。整个过程的时间复杂度是 O(NKlogK)空间复杂度是 O(K)。这个变体考察的就是你有没有把“双链表合并”推广到“多路归并”的能力。5.3 变体二两个有序数组的合并如果把链表换成数组同样的归并思想同样适用。数组的合并需要额外开一个大小为 mn 的结果数组然后用三个下标i、j、k分别指向数组1、数组2、结果数组的当前位置。这里最经典的变体是“合并两个有序数组要求结果保存在第一个数组中”这需要从两个数组的末尾往前扫描避免覆盖尚未处理的元素。这个套路在 LeetCode 和各类图书里都有很多同学数据结构课上都见过。链表合并和数组合并的核心是一致的两个指针或下标各自维护当前待比较位置每次取出较小者放入结果容器。理解了这一点不管题目怎么换包装你都能抓住它的主干。5.4 各种改法逆序、去重、查找交点除了合并本身这道题还能延伸出不少相关考点合并后去除重复元素比较时如果发现前后两个节点值相等跳过其中一个即可判断两条链表是否相交先分别计算两条链表长度让长链表先走差值步然后同步遍历比较节点地址找出两条链表的中间节点用快慢指针快指针每次走两步慢指针每次走一步快指针到末尾时慢指针正好在中间逆序链表用三个指针原地反转或者用头插法建新链表这些变体本质上都是链表的指针操作练熟一道合并题等于把这些门道都过了一遍。5.5 对这门课整体定位的一点看法数据结构这门课说到底是教人怎么组织和管理数据。线性结构是第一章链表是线性结构里最灵活、也最容易出错的一种存储方式。很多人觉得链表难不是因为它语法复杂而是因为必须在脑内维护一个“节点 指针”的抽象模型。这道合并题恰好是所有链表操作里最典型的一个它同时包含了遍历、比较、插入、节点拼接四种基础操作还把尾插法、哨兵节点这些重要技巧全部串联了起来。我在实际写代码时养成的一个习惯是每次写完一个链表函数都要在心里默问一句“如果这个链表是空的怎么办”“如果这个操作发生在最后一个节点上怎么办”“如果我想保持稳定性比较符号写对了吗”这三个问题一过大部分边界 bug 都能提前暴露。这个习惯也推荐给你。把这道题真正吃透之后你再看后面的二叉树、图、哈希表会发现很多操作的本质还是“用一个指针或索引在元素之间移动、比较、链接”。数据结构的东西是一通百通的而这第一关值得你慢慢磨。