题目是“习题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(n+m)降到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(m+n)，m和n分别是两个链表的长度。空间复杂度则取决于写法：
- 如果新建链表且每个结点都新malloc，空间复杂度是O(m+n)
- 如果复用原有结点，只改变指针指向，额外空间复杂度是O(1)
这里我想强调一个容易被忽略的点：“新建链表”不一定要新malloc结点。你可以把A、B的结点取下来，重新搭一个链表C，这本质上只花了O(1)的额外空间，只是改变了链表结点的归属。严格说这不是“新建”，而是“重组”。如果面试官问“能不能O(1)空间实现”，你要理解他问的是能否不新开结点、只改指针，那答案就是上面那两种写法都可以算O(1)，只要你没有为结果链表重新分配结点。
另外，如果你用的是普通的迭代写法，时间复杂度和递归写法一致，区别只在于递归会消耗系统栈空间（深度为O(m+n)），而迭代则没有这个问题。下文讲递归时我会再详细展开。
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，所以如果代码顺序是“先pa=pa->next，再tail->next=pa”，反而会丢。正确的顺序一定是：先保存/移动指针，再接链。
再提供一套我觉得最不容易出错的“接结点四步法”：
- 用临时指针tmp保存将要接入结点的后继：
LNode *next = pa->next; - 把结点接入：
tail->next = pa; - 更新tail：
tail = 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)的角度去回答。
第四，如果你用的是带头结点的链表，千万不要忘记给头结点分配空间。这是我在前面也强调过的，但即使是我，偶尔也会因为切换到不带头结点的代码模板而重新犯这个错。建议你平时练习时就固定一个习惯：要么全用带头结点，要么全用不带头结点，不要在同一个程序里混用，否则很容易弄混头指针和第一个数据结点的概念。
最后再说一个小技巧：很多同学以为“两个有序链表合并”必须同时遍历到两个链表都为空才算完，其实完全没必要。因为只要有一个链表走完了，剩下的那条链表直接整体接上就可以了。这个“提前退出”的优化，我称之为“归并收尾用甩接”，代码简洁且不会出错，也是面试官期待看到的优化点之一。
这道题我前前后后在不同场合写了不下几十遍，每次写都有新体会。希望你也能把它练成肌肉记忆一样的基本功，后续遇到更复杂的链表题时，会感谢自己今天花了这一小时把它彻底搞明白。