1. 这道题为什么值得认真对待先亮明身份我是常年和数据结构、算法题打交道的工程师。带过的实习生、考研的学生、面试的人里十个有七个会在两个有序链表合并这道题上栽跟头。题目本身简单到一句话能说清——把两个递增有序的链表合并成一个新的递增有序链表——但往往越是这种题越能暴露一个人对指针、边界条件、内存管理的理解是否扎实。我第一次认真做这道题是在准备考研专业课的时候。当时《数据结构》教材的链表章节排在绪论之后习题2.5就是这道题。说实话那时候我照着答案抄了一遍以为自己会了。直到后来在项目里写归并排序的链表版本被一个少移动tail指针的bug折磨了两个小时才意识到当初根本没学透。这道题最大的价值在于它是归并排序的merge操作在链表形态下的最小实现。归并排序大家都知道把数组拆成两半分别排序再合并。换成链表时拆分和合并的形态会有变化但合并两个有序序列这一步是完全一样的。外面那些更复杂的东西——多路归并排序、外部排序里的归并阶段、数据库里的merge join操作——内核都是这道题。所以你不把这道题吃透后面会遇到一连串麻烦。再说直白一点LeetCode上的第21题Merge Two Sorted Lists就是这道题。大厂面试手撕算法时考它不是因为题难而是因为代码量小、涵盖的知识点足够多能快速看出你会不会用哨兵节点/虚拟头节点、懂不懂避免无效判断、写出来的代码是否简洁可维护。这篇文章里我会把我实际写过、调试过、总结过的全部经验放出来包括迭代解法和递归解法的代码、各种隐藏的边界条件、测试用例怎么设计、以及我踩过的所有坑。不需要特别深的功底只要你懂链表的基本概念就能跟上。2. 先理清题目里三个容易被忽略的隐性条件2.1 利用原有结点和新建链表是两种完全不同的写法很多同学第一次看到这道题第一反应是把两个链表的值拷贝出来放进一个新链表。这样真做出来从输出结果上看没错但这恰恰是教材习题最想考察的反面。考研教材里这道题的原文一般会带一句要求利用原表的结点空间不额外申请新的结点。意思是你只能在原有节点之间改连线不能malloc新节点来保存数据。这道题考察的是指针重接不是值拷贝。为什么这么要求一方面是为了考察你是否理解链表在内存里是怎么存数据的——节点分散在各个地址上只能通过next把前后关系串起来合并的本质就是改变next的指向另一方面是空间复杂度的要求O(1)的辅助空间而不是O(nm)的新空间。你要是用数组或者新建节点去做功能上没错但违背了这个题目考察的意图考试时至少要扣分。2.2 带头结点还是不带头结点处理方式不一样这是习题和LeetCode之间最大的差异之一。国内教材的链表题绝大部分默认带头结点。头结点是一个不存数据的节点它存在的意义是让链表的删除、插入操作不需要区分删第一个节点和删中间节点统一处理。而LeetCode版本是不带头结点的直接给你第一个数据节点的指针。这两种形式下合并逻辑的主干一样差别体现在初始化和返回头上。带头结点的写法往往是把其中一个链表的头结点直接拿过来当作结果链表的头结点使用最后返回这个头结点不带头结点的写法通常需要创建一个临时的虚拟头节点dummy node站在最前面把合并后的节点一个个挂上去最后返回dummy的next。我建议你把两种都写一遍。因为面试时你遇到的输入不一定是什么形式如果你只会LeetCode版的dummy写法遇到带头结点、且要求你用原来头结点的说法就会不知所措。2.3 相同元素保留还是去掉决定了比较符号题目里只说了有序没说是否有重复值。经典的合并要求是合并后仍然递增有序如果两个链表里有相等的值它们都要出现在结果里。比如链表A有1、3链表B有3、5合并结果是1、3、3、5。这时候写代码就比较稳妥了if (p-data q-data)注意这里用的是。用小于等于当p和q指向的值相等时优先取p那边的节点。这样写不会漏数据。如果你用了相等时取else分支逻辑上也没错结果还是有序的但相等值从哪边取就变得不直观了。当然我说的是标准练习题的做法如果题目明确要求去重那又是另一套写法了。还有一个小细节如果两个链表本来就是各自递增的用能保证合并后相同值的相对顺序和原来一致这在某些场景下算是稳定排序性质。教材上一般不特意强调但你心里有数就好。2.4 链表节点的基本定义下面代码是我这篇文章里统一用的节点定义带头和不带头场景我都基于它。如果你用的是C可以写成struct的构造函数形式但C语言的写法更有助于看清内存操作typedef struct LNode { int data; struct LNode *next; } LNode;3. 迭代解法把接线这个动作写干净3.1 核心思路双指针交替指向较小节点迭代解法是整个题目最推荐的写法它思路直接、空间复杂度O(1)、适合链表长度很大的场景。我们先说不带头结点的情况。假设你有两个链表的头指针list1和list2它们都指向第一个数据节点。合并的过程可以想象成两个队伍的人往一条新队伍里排队队伍A和队伍B各派出一人站在队首谁的值小谁先出列站到新队伍末尾然后它背后的那个人顶上继续比较。用代码表示需要一个虚拟头节点来起步struct ListNode { int val; struct ListNode *next; }; struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { struct ListNode dummy; // 虚拟头节点栈上分配 struct ListNode* tail dummy; // tail始终指向结果链表的最后一个节点 dummy.next NULL; while (list1 list2) { if (list1-val list2-val) { tail-next list1; list1 list1-next; } else { tail-next list2; list2 list2-next; } tail tail-next; // 这一步非常容易忘 } // 循环结束后一个链表已经走完另一个可能还有剩余节点 tail-next list1 ? list1 : list2; return dummy.next; }3.2 为什么非要用虚拟头节点很多人一开始会写这样的代码先判断list1-val和list2-val哪个小把结果链表的头指针指向小的那个然后再进入循环。这样写有一个麻烦结果链表的第一个节点需要单独处理循环体内变成先接节点、再判断是否是第一个节点。虚拟头节点的核心思想就是让第一个节点和后面的节点享受同样的处理逻辑。它本身不存数据它存在的唯一意义是让tail-next在一开始有一个确定的指向位置。因为我们的返回值是dummy.next所以这个虚拟节点不会被带出去。它就像一个临时垫在底下的桌垫桌布铺好了垫子自然可以留在原地。这里有个小细节dummy直接定义成结构体而不是malloc出来的指针。原因很简单虚拟头节点不需要长期存活函数栈上定义它生命周期正好覆盖整个函数执行期间函数返回后自动失效不用手动free不会泄漏内存。如果你习惯用malloc创建虚拟头节点在返回结果前得先free掉它否则每次合并都会泄漏一个节点大小的内存积少成多就很麻烦。3.3 循环结束后的那一步到底在干什么循环条件是while (list1 list2)只要两个链表都没走完就一直比较、接线。循环退出时一定有一个链表走到了末尾指针为NULL另一个链表可能还剩一串节点也可能也刚好走完。关键点来了剩下的那一整串节点本身就是有序的而且它们的值一定都不小于已经合并好的最后一个节点的值。比如链表A是1、3、5、7链表B是2、4、6。走完循环后链表B的6被接进去链表A还剩7。此时不需要再比较、再调整直接把tail的next指向剩下那个7即可。如果你还在傻傻循环去逐个比较说明你对有序这个前提条件利用得不够充分这是很多初学者的通病。3.4 带头结点场景的另一种写法如果题目明确说链表带头结点而且要求不额外申请节点最经典的做法是以A的头结点作为C的头结点最后释放B的头结点。这种写法在考研习题答案里经常出现也是我当年被老师重点要求背下来的版本LNode* mergeTwoLists(LNode* La, LNode* Lb) { LNode* tail La; // 用A的头结点作为结果链表的头 LNode* p La-next; LNode* q Lb-next; while (p q) { if (p-data q-data) { tail-next p; p p-next; } else { tail-next q; q q-next; } tail tail-next; } tail-next p ? p : q; free(Lb); // B的头结点已经没用了释放掉 return La; // 结果链表的头结点就是A原来的头结点 }我明确说一下这个写法有个副作用原链表A和B的数据节点都被重新连到了同一个链表里你再也无法通过La或Lb的头指针单独访问原来的链表了。如果你后续还想用原来的链表就要小心。面试时主动跟面试官确认这个合并是否允许修改原链表是很加分的交流因为很多人不会意识到这点。3.5 时间复杂度和空间复杂度时间上每个节点最多被比较一次、被接线一次总耗时O(mn)其中m和n是两个链表的长度。空间上只用了几个指针变量和一个栈上的虚拟节点头辅助空间是O(1)。这就是这道题最理想的状态时间线性空间常数。4. 递归解法公式化写法但要警惕递归深度4.1 先写核心递归公式递归解法很多人觉得难但它其实有一个很好记的公式。有函数merge(a, b)返回的是合并a和b两个链表后的头节点。如果a为空返回b如果b为空返回a如果a的值较小那么最终结果的头节点是aa的next应该指向merge(a-next, b)的结果如果b的值较小或相等那么最终结果的头节点是bb的next应该指向merge(a, b-next)的结果翻译成C语言struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { if (!list1) return list2; if (!list2) return list1; if (list1-val list2-val) { list1-next mergeTwoLists(list1-next, list2); return list1; } else { list2-next mergeTwoLists(list1, list2-next); return list2; } }这段代码的递归深度是O(mn)。每次递归调用时会把当前比较较小值的函数状态压入调用栈等递归返回后再一层层释放。链表长度几百个节点根本感觉不到但如果你在真实项目里合并一个十万节点的链表就很容易把栈空间打爆导致程序崩溃。这就是为什么我在生产代码里几乎不用递归写法但在笔试、面试的时候我仍然建议你先把递归版本写出来。4.2 为什么很多教材推荐递归写法因为代码短、和自然语言描述几乎一一对应便于阅卷老师快速看懂你的思路。很多考研真题的标准答案就是递归写法你不背下来考试时临时想迭代版本虽然也能写但代码长度更长出错概率更高。而且递归写法的核心逻辑非常漂亮它把合并两个链表的问题不断化简成合并更小的链表的问题。每递归一层至少有一个链表往前推进一个节点所以总能在有限层数内结束。4.3 递归的三个坑第一个坑忘记终止条件。如果不在函数开头判断list1或list2为空就返回另一个递归永远不会结束直接栈溢出。第二个坑没有把返回值接好。很多人写递归时只做了if (list1-val list2-val) return list1;忘了把list1-next指向递归结果。这样合并不完整后面所有节点都丢了。第三个坑递归深度。前面说了深度是O(mn)。实际开发中如果一个链表有几万甚至几十万个节点我强烈建议你用迭代版本。写递归版本前先问自己一句话这个链表的长度会不会超过栈空间能承受的规模如果会别用递归。5. 测试用例设计把边界情况一次测透5.1 为什么功能对了还要专门设计测试很多同学写完代码拿题目给的示例一跑输出对了就觉得完成了。问题在于题目给的示例通常只有一两个覆盖不到空链表、长度不一致、值全部相等这些边界场景。我在实际写这道题的时候吃过一次亏核心逻辑没问题但忘了处理list1和list2都为空的场景运行到if (list1-val list2-val)时直接段错误。从那以后我给自己定了一个规矩凡是写链表类题目必须设计一套覆盖主要边界的测试用例。与其说这是为了考试不如说是在培养一种工程思维——你写的代码最终是要被别人调用的调用者不一定会按你的假设传参。5.2 六组经典边界用例我建议按下面这个表格来清点测试用例用例编号链表A链表B预期合并结果为什么值得测1空空空验证空指针处理2空55验证一空一非空3121, 2基本比较逻辑4111, 1相等值是否保留51, 3, 52, 4, 61, 2, 3, 4, 5, 6交替交叉核心场景61, 23, 4, 51, 2, 3, 4, 5一个链表全部小于另一个第六组尤其容易被忽略。很多人测试时只想到交替插入没想到一个链表整体小于另一个。如果主循环结束后你没有拼接剩余节点的代码这种情况会丢数据。测试用例设计得越全面你代码里的bug被强行暴露得越早这是省时间的策略。5.3 一个可以直接拿来用的测试骨架我平时写链表题都会先写三个工具函数buildList构造链表、printList打印链表、freeList释放链表。这几个函数几乎不会变写完一次可以到处复用。下面是一个C语言写的完整测试骨架#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node; Node* buildList(int arr[], int n) { Node dummy; dummy.next NULL; Node* tail dummy; for (int i 0; i n; i) { Node* node (Node*)malloc(sizeof(Node)); node-data arr[i]; node-next NULL; tail-next node; tail node; } return dummy.next; } void printList(Node* head) { while (head) { printf(%d - , head-data); head head-next; } printf(NULL\n); } void freeList(Node* head) { while (head) { Node* tmp head; head head-next; free(tmp); } } int main() { int a[] {1, 3, 5}; int b[] {2, 4, 6}; Node* listA buildList(a, 3); Node* listB buildList(b, 3); Node* merged mergeTwoLists(listA, listB); printList(merged); // 期望输出: 1 - 2 - 3 - 4 - 5 - 6 - NULL freeList(merged); // 合并后原链表节点已混在一起统一释放合并链表即可 return 0; }注意最后一行的注释因为你复用了原节点合并后listA和listB里的所有节点都串到了merged上所以不能再单独freeList(listA)和freeList(listB)否则同一个节点被释放两次。要么你只释放merged要么你压根别调用freeList。这是链表题里特别常见的内存管理陷阱。5.4 断言帮你自动检查结果上面用printList肉眼核对结果终归是人工的。我更推荐在测试里加上断言让程序自己判断合并结果对不对。尤其当你后面要写更复杂的变体比如k路归并时断言能节省大量人力。int checkResult(Node* head, int expected[], int n) { for (int i 0; i n; i) { if (!head || head-data ! expected[i]) return 0; head head-next; } return head NULL; }然后在main里写int expected[] {1, 2, 3, 4, 5, 6}; if (checkResult(merged, expected, 6)) { printf(test passed\n); } else { printf(test failed\n); }这比肉眼盯着终端强多了。代码一旦改动跑一遍测试就能立刻发现问题。6. 最容易踩的坑和我的调试经验6.1 五个真实的翻车现场这道题代码短但坑很密集。我把自己踩过、以及帮别人排查过的常见问题整理成下面几类忘记移动tail指针。很多人写完tail-next p或者tail-next q后没有执行tail tail-next。结果就是结果链表永远只有最后一个被接进去的节点前面的节点全部丢了。这个错误的隐蔽之处在于如果两个链表只有一个节点你根本看不出来问题——因为每次接完节点后tail本来就指向结果链表的最后一个节点不需要再移动。但节点一多立刻出bug。循环结束后没拼接剩余链表。如果在while (p q)结束后直接返回head链表较长时大概率丢数据。正确写法我已经强调过tail-next p ? p : q这一行必须加。带头结点时没有跳过数据节点。有人写p La而不是La-next把带头结点的头结点data也当作数据参与比较。头结点data通常没初始化是个无意义的值结果链表里会出现一个脏数据节点。递归版本没有处理空链表终止条件。开头就判断if (!list1) return list2;和if (!list2) return list1;不能少顺序也不能颠倒。没有意识到原链表结构被改变。函数执行完你拿着原来的listA头指针去遍历会发现链表变短了甚至节点顺序也乱了。这不是bug而是复用原节点这种设计本身的副作用。如果你希望合并后原链表还能用唯一办法是复制节点新分配内存。面试时最好主动说明这一点。6.2 调试链表问题的杀手锏指针快照链表出问题时靠脑子想象很难定位。我教你一个土办法在关键步骤打印当前三个指针各自指向的节点以及结果链表已经连好的部分。不需要什么复杂工具printf就够了。void debugSnapshot(Node* p, Node* q, Node* tail) { printf(p%d, q%d, tail%d\n, p ? p-data : -1, q ? q-data : -1, tail ? tail-data : -1); }在tail-next ...这一行前后各调用一次你能清楚看出每次循环里p、q、tail的移动是否符合预期。如果tail的值连续两次一样说明你忘了移动tail。另外我建议在打印链表时不要只打印data最好把节点的地址也打出来。比如void printListWithAddr(Node* head) { while (head) { printf(%d(%p) - , head-data, head); head head-next; } printf(NULL\n); }为什么要打地址因为链表是靠指针连接的结构你光看值看不出有没有形成环。如果出现死循环多半是某个节点的next指回了自己或者之前的节点。打印地址后你一眼就能看出有没有重复的节点地址出现。6.3 内存泄漏和重复释放的检测C语言链表题最常见的隐藏问题就是内存泄漏和重复释放。一次合并泄漏一个头节点看似无伤大雅但如果这个函数在一个循环里被调用十万次就是一个大瓶颈。如果你用Linux可以拿valgrind跑一下测试程序gcc -g merge.c -o merge valgrind --leak-checkfull ./merge如果有泄漏valgrind会明确告诉你哪一行malloc的节点没有被free。如果是重复释放valgrind会直接报Invalid free。如果环境是macOS不习惯装valgrind也可以用clang的地址消毒器AddressSanitizer编译clang -fsanitizeaddress -g merge.c -o merge ./merge地址消毒器会实时检测到堆缓冲区溢出、重复free、内存泄漏这类问题比valgrind更快、更直观。我强烈建议你在本地练这道题时默认开启ASan它能帮你避免很多隐性内存错误。6.4 一个小习惯写函数前先回答三个问题我现在每次写这种改链表结构的函数都强迫自己在脑子里回答三个问题函数的返回值是什么新链表的头节点还是原链表的头节点函数会不会修改输入链表如果会调用方是否允许虚拟头节点/辅助节点应该在栈上创建还是堆上创建谁负责释放这三个问题答案想清楚写出来的代码基本不会出现重大方向性错误。这道题尤其适用。很多同学写错不是因为语法不熟而是没想清楚这三个问题就开始动笔写着写着就乱了。7. 从两路合并到K路归并一题带出整个归并家族7.1 归并排序的链表版本离不开它归并排序的核心步骤就两个分割和合并。数组版本的分割靠索引链表版本的分割用快慢指针找中点。找到中点后把左右两半分别排序最后就是你写的这道题的合并操作。所以如果你能把这道题练得炉火纯青再去写链表的归并排序只是多写了快慢指针找中点和递归排序两个子链表这两个部分merge部分直接复用。这也是我把这道题当成归并家族的地基来对待的原因。7.2 两路扩展到K路的思路真实场景中往往不是合并两个有序链表而是合并K个。比如外部排序里内存读不下所有数据就把数据分成K个有序段每次从每个段里取最小的记录合并成一个更大的有序结果。这种场景下两路合并的思路可以推广。朴素做法是每次比较K个头节点选出最小值接上去。这样选出N个节点每次比较K次总复杂度O(NK)。当K很大时效率明显变差于是就要用最小堆把K个头节点的值都塞进一个小顶堆每次弹出堆顶元素代表的最小值然后从它所在的链表拉下一个新节点进堆直到堆空。选最小值从O(K)降到O(logK)总体复杂度O(N logK)。这里面的核心思路和两路合并一脉相承你还是一遍遍从候选节点头里选最小的那个只是选择工具从直接比较两个换成了堆。掌握了这道题的基本逻辑学习K路归并时你理解得会快得多。7.3 实际项目里我还用它做过什么除了算法题我在业务代码里也用过类似的合并逻辑。有一段时间做数据导入功能需要把两个不同来源但都已经排好序的文件合并成一个升序文件。文件太大不能全部读进内存我就是用这种双路归并的方式分别打开两个文件每次读取当前行比较后写入结果文件谁小谁前进。这就是这道题从链表形态迁移到IO流形态的样子。还有一次处理多个独立时间段列表的合并每个列表内部按开始时间排好序需要合并成一个总时间线。当时的实现逻辑和链表合并几乎一一对应只是节点换成了结构体对象指针换成了数组下标。所以不要小看这道小题它的思想真的会渗透到各种看起来八竿子打不着的地方。最后分享一个我个人的习惯每学一道经典算法题我都会把两个版本迭代版和递归版都写一遍并配上一套边界测试用例。这个习惯帮我省下过大量面试前临时抱佛脚的时间。这道题是我练习清单里出现频率最高的一道也希望它成为你的工具箱里顺手的那把好工具。