如果你刚开始刷LeetCode或者正准备面试却被“链表”相关题目卡住那合并两个有序链表这道题几乎算得上必刷清单里的第一道拦路虎。它在LeetCode上是第21题难度标着Easy但每年面试手撕环节里出现的频率一点不比Medium低。原因很直接这道题规模不大却把链表遍历、指针移动、节点拼接、边界处理这些基础动作全考了一遍。很多人静态看题解觉得“就这”一上机自己写就懵指针一多就不知道自己指到哪儿了。这篇文章我会用C语言从题目本身的含义开始把常见解法背后的取舍讲清楚再一步步拆解完整代码最后把几个我真实踩过的坑整理给你。文章适合刚开始刷题的大学生、准备校招的应届生也适合想回头夯实链表基本功的开发者。只要你认真跟着走一遍这道题完全可以成为你“吃透链表”的起点。1. 先理解这道题到底在考什么1.1 题目本质把两条“有序链”织成一条题目给两个链表比如list1是 1-2-4list2是 1-3-4要求合并成一条新的升序链表节点值从小到大排。最简单粗暴的做法是把两个链表里的值都读出来放进数组排序后再重新建链表但这么做一来浪费额外空间二来完全脱离了链表操作的初衷。真正让你练的是“原地穿针引线”通过改变节点的next指针把两条已有的链按顺序串起来而不是去创建一堆新节点。这个思路本质上和归并排序里的merge过程一模一样两个有序数组归并时用两个下标扫谁小先取谁两个有序链表归并时用两个指针扫谁小先接谁。区别只在于数组用下标移动链表用指针移动数组直接赋值链表要动next。理解了这一层你不仅会做这一道题后面遇到“合并K个有序链表”“链表归并排序”这类变体底子也就在这里打好了。1.2 为什么这道题是“链表入门必刷”我见过不少同学链表基础操作单独拎出来都知道会遍历会插入会删除。可一旦题目把它们组合起来就不知道从哪儿下手了。这道题妙就妙在它把链表最基本的几个操作全部揉在一起两个链表同时遍历、逐个比较节点值、把较小节点接入新链、最后接上剩余部分。完成它你其实一次性练熟了链表操作的“读、比、接、移”四件事。另外一点很实际面试官喜欢用这道题考察候选人的代码习惯。因为它的逻辑不算复杂正好看出你写指针时会不会下意识做空判断会不会处理“第一个节点谁来当头”这种细节会不会在循环结束后忘记把剩余链表接上。这些问题不是背一道题就能解决的而是要靠理解每一步为什么这么写。所以接下来我不打算直接甩代码而是先把两条主流解法的思路掰开揉碎讲清楚。2. 解题方案迭代法还是递归法2.1 迭代法虚拟头节点撑起全局迭代法的核心思路是维护三个指针p1负责扫list1p2负责扫list2cur负责指向新链表的尾部。每一步比较p1和p2指向的节点值值较小的那个节点就“嫁”到cur后面然后对应指针后移一位cur也后移到新接上的节点。循环一直进行到某一方链表先走完此时剩下那条链的剩余部分整体接到cur后面因为剩余部分本身就是有序的不需要再逐个比较。这里有个非常关键的细节新链表一开始是空的cur该指向哪里如果直接把cur初始化为NULL那么第一个节点接入时要单独判断“是不是第一个节点”代码会多一个分支而且容易出错。更聪明的做法是创建一个虚拟头节点dummy让dummy-next指向真正的头节点cur初始指向dummy。这样无论第一个节点从哪里来操作方式都和其他节点完全一致统一走“cur-next 待接入节点”这条路最后返回dummy-next就是结果链表。为了这一个细节代码的健壮性和可读性会提高不少面试时也能减少不必要的分支逻辑。2.2 递归法代码极短但别盲目用递归解法的思路更简洁merge(l1, l2)这个函数像在问“谁当头”。如果l1为空直接返回l2如果l2为空直接返回l1。假设l1当前节点的值更小那么头节点就是l1接下来要解决的是“l1-next 和 l2 这两个链表怎么合并”于是递归调用merge(l1-next, l2)把结果接到l1-next上最后return l1。反过来如果l2更小对称地处理。这么写下来代码十几行就能搞定看起来非常优雅。但这里的代价藏在系统栈里。递归的深度取决于两个链表的长度之和极端情况下如果链表很长栈的消耗会很可观甚至造成栈溢出。LeetCode的默认测试数据一般不会变态到那种程度但面试时如果你一上来就用递归面试官很可能会追问“空间复杂度是多少”这时候你要能答出递归栈的开销否则容易挂。在我看来递归解法适合用来检验你对递归逻辑的理解面试时可以作为备选方案讲一讲但平时练习和实际项目里迭代法是更稳妥的选择。2.3 我的选型建议直接说结论初学者优先掌握迭代法把它写到能闭着眼默出来的程度递归法可以等迭代熟练后作为思维训练再补上。两种方案的时间复杂度都是O(n m)其中n和m分别是两条链表的长度因为每个节点最多被比较一次。空间复杂度上迭代法只需要常数个指针变量是O(1)递归法则要消耗O(n m)的递归栈空间。两张方案的对比我整理成表格方便你一眼看清差异对比维度迭代法递归法时间复杂度O(n m)O(n m)空间复杂度O(1)O(n m)代码长度约20行约10行理解难度直观适合入门需要理解递归出口面试推荐度高稳扎稳打中可作为加分项从实战角度讲面试手撕代码的时候迭代法不容易写错逻辑也方便跟面试官逐步解释。递归虽然短但如果你没讲清楚递归的出口和返回值含义反而容易让面试官觉得你在背答案。道理都说明白了下面进入正题用C语言把迭代法写出来。3. C语言完整实现与核心代码逐段拆解3.1 链表节点的标准定义LeetCode的链表题在C语言环境下节点定义一般是这样的struct ListNode { int val; struct ListNode *next; };这是最基础的单链表节点结构。val存值next存下一个节点的地址。合并两个有序链表所有操作都是围绕next指针做文章。有一点值得注意题目并没有要求你新建节点来存储合并后的值所以标准的解法是直接复用两个原链表中的节点只改变它们的next指向而不是malloc一堆新节点。这一点很多初学者容易搞混以为合并就要新建链表其实在链表的世界里“拼接”往往比“新建”更常见也更高效。3.2 为什么要引入虚拟头节点前面提过虚拟头节点这里展开说清楚它到底解决了什么实际问题。如果不使用虚拟头节点合并后链表的第一个节点可能是list1的头节点也可能是list2的头节点取决于谁的值更小。这导致你没法用一个统一的操作处理“第一个节点谁来当head”要么先比较一次单独赋值要么就得多写一个if分支。这种分支逻辑在只有两个链表时还勉强能忍但如果以后让你写合并K个链表的代码这类特殊处理会变得非常啰嗦。虚拟头节点的做法相当于给新链表临时安了一个“第0个节点”。用一个ListNode类型的变量dummy它的val没有任何实际意义只为了让cur有一个确定的起点。所有节点接入操作都统一写成cur-next xxx循环结束后再返回dummy.next那个“第0个节点”就自动被跳过去了。这种“哨兵”思想在很多链表题里都适用比如删除链表的倒数第N个节点、两两交换链表节点所以我建议你把虚拟头节点当成一个常规工具记下来遇到链表操作不确定头节点时先问自己一句“这里能不能用到dummy”。3.3 完整代码先睹为快下面是迭代法在C语言里的标准写法struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { struct ListNode dummy; dummy.val 0; dummy.next NULL; struct ListNode* cur dummy; while (list1 ! NULL list2 ! NULL) { if (list1-val list2-val) { cur-next list1; list1 list1-next; } else { cur-next list2; list2 list2-next; } cur cur-next; } if (list1 ! NULL) { cur-next list1; } if (list2 ! NULL) { cur-next list2; } return dummy.next; }这份代码在LeetCode上可以直接通过。和很多教程里用malloc创建虚拟头节点的写法不同我这里直接在栈上定义了一个dummy变量省去了一次malloc和对应的free也不会因为忘记释放而造成内存泄漏。栈上的变量虽然不能像堆内存那样长期存在但在这个函数范围内它的生命周期完全够用函数返回后它的地址不会再被使用不会有悬垂指针问题。3.4 逐行拆解每一步都要知道为什么先看虚拟头节点和cur指针的初始化。dummy放在栈上dummy.next初始化为NULL是防止后续操作访问到不确定的野指针。cur指向dummy含义是“新链表的当前尾节点”因为新链表此刻为空dummy就是它实际的尾部。这一步是整段代码的地基cur指向哪里下一次节点就接到哪里。再看while循环。条件是两个指针都不为空也就是说只有当两条链表都还有剩余节点时才需要比较大小。循环体里的if分支本质上是在回答“当前两个候选节点谁更小”。如果list1的当前节点值更小就把这个节点从list1里“拆”下来接在cur后面然后list1指针后移一位。else分支则处理list2也包含两个节点值相等的情况值相等时接list2也可以不会破坏升序要求。每次接入节点后cur都要往后走一步让自己始终指向新链表真正的尾节点这个过程一定不能遗漏否则下一次接入会覆盖上一次的结果。循环结束后一定有一条链表先走完另一条还剩下一串节点。这里就需要把剩余部分整体接入。为什么可以直接接整个链表而不是继续逐个比较因为剩余部分的链表本来就是有序的而当前新链表的所有节点都小于剩余部分的第一个节点所以剩下的整条链接在cur后面依然整体有序。这也是归并思想里最核心的一条两个有序子序列合并时一部分耗尽后另一部分的剩余序列直接拷贝即可。代码里写了两个if实际上由于while结束必然至少有一个指针为空这两个if最多只有一个会生效不会出现两边都剩余的情况。3.5 把“交接”过程画在心里指针操作的每一步本质上都是“拆旧链、接新链”。当list1的节点被接到新链表时list1-next指针并没有被改动我们只是把cur-next指向了list1然后让list1指针移动到原链表的下一个节点。这相当于在逻辑上把节点从原链表“摘”下来送进新链表但原链表的结构其实还保持着只是遍历指针绕过了它。这一点很反直觉也经常让初学者想不通我没动list1-next它怎么就不在原链表里了因为你已经没有任何指针指向这个节点的“前一个位置”了。链表是一种“从前往后找”的结构当你失去了到达某个节点的路径它在你的遍历世界里就已经被移除了。4. 常见错误、调试技巧与面试延伸4.1 我替你踩过的那些坑这段代码虽然短但新手写出来的bug种类一点都不少。我列了一张高频错误速查表基本上覆盖了我平时答疑时见到的绝大多数问题错误表现根本原因解决办法程序死循环一直转不结束循环体内忘记移动list1或list2指针每次接入节点后让对应链表指针后移一位返回结果只有第一个节点循环体内忘记移动curcur始终要指向当前尾节点返回NULL或者编译警告返回了dummy变量本身而不是dummy.next记住返回值是合并后链表的头指针出现随机地址/段错误虚拟头节点用malloc却没初始化next初始化dummy.next NULL栈上变量也同理值相等时逻辑混乱没想清楚等于号归到哪个分支用else统一处理list1list2的情况多了一个头节点把dummy也当成了结果链的一部分画图确认返回地点是dummy.next我最常看到的就是有人把list指针移动这件事忘掉。他们写了cur-next list1但忘了写list1 list1-next结果每次循环都是同一个节点接上来链表陷入无限循环。这种问题靠读代码很难一眼发现我建议你画一个三行的小图第一行是list1的链第二行是list2的链第三行是新链表每一步把箭头更新一下比你盯着代码空想有效得多。4.2 链表程序就该这么调试链表题光靠printf大法也能调但要想更高效我建议你写两个工具函数专门伺候调试。一个函数负责把一个链表完整打印出来方便你看合并前后的变化void printList(struct ListNode* head) { while (head ! NULL) { printf(%d - , head-val); head head-next; } printf(NULL\n); }另一个函数负责按数组快速构造一个链表让你可以轻松制造各种测试数据struct ListNode* createList(int arr[], int size) { struct ListNode dummy; dummy.next NULL; struct ListNode* cur dummy; for (int i 0; i size; i) { struct ListNode* node (struct ListNode*)malloc(sizeof(struct ListNode)); node-val arr[i]; node-next NULL; cur-next node; cur node; } return dummy.next; }有了这两个函数测试就变得非常方便。你可以在main里构造几个典型用例两个都为空、一个为空、两个长度不相等、两个链表值全都相等、第一个链表所有节点都小于第二个链表……这些用例覆盖了所有边界情况每遇到一个bug先看打印结果哪一步和预期不符再回到代码里对照。调试链表时还有一个实用技巧如果你怀疑某次赋值后链表结构出了问题可以在关键赋值语句后面用printf输出cur、list1、list2三个指针当前指向的节点值一眼就能看出是哪个指针没走。4.3 时间和空间的复杂度到底怎么算这道题的复杂度分析很适合当作面试口头考察题。时间上两个链表各被遍历一遍而每条链表的节点最多只会被“看一眼”并接入一次所以总时间是O(n m)。空间上迭代法只用了dummy和cur两个栈上变量再算上出入函数的开销是严格的O(1)辅助空间这比递归法需要O(n m)的栈空间要漂亮得多。面试时你说清楚这一点比单纯报出“时间复杂度O(nm)”要更能体现功底。要注意的是LeetCode提交时不会因为你的递归写法空间浪费而判错但面试官介意的是你有没有复杂度意识。建议你形成习惯写完任何算法题都主动在脑子里跑一遍复杂度分析时间空间各报一次这比刷题数量更能拉开差距。4.4 从这一题延伸出去的方向这道题吃透了可以往不少方向延伸。最简单的变体是把“两个有序链表”变成“K个有序链表”LeetCode第23题就是那个版本解法从两两合并进阶到用最小堆维护K个候选节点核心还是“比较谁最小”。另一个方向是把链表改成数组归并两个有序数组的思路几乎一样只是数组需要从后往前填来避免覆盖。再进一步合并排序在链表上的实现也依赖这个merge过程先在链表中间切开递归排序左右半部分再用这里的merge组合起来。所以这道题看起来不起眼实际是整个链表归并体系的基石。5. 写在最后几个让你少走弯路的实操心得我最后想分享几个自己实战中沉淀下来的小习惯。第一个习惯是链表题永远先画图再写代码哪怕只是在草稿纸上画三个圈三根线。几乎百分之八十的链表bug都可以靠画图提前消灭因为指针操作一旦超过两步人脑很容易被“当前状态”和“下一步状态”搞混。第二个习惯是写完代码先跑空链表、单节点链表、值全部相同这三组特例再跑正常用例这道题虽然简单但边界条件几十种组合提前测一遍能让自己心里有底。第三个习惯可能有点反常识尽量少用malloc创建临时哨兵节点。我早期写链表题总是习惯给虚拟头节点开一份堆内存然后写完就忘了freeLeetCode模式看不出来但到了实际工程里就是妥妥的内存泄漏。后来我改成在栈上定义dummy直接传地址给指针省一次分配就少一个泄漏隐患。栈上的dummy生命周期短但正好和函数调用周期匹配不会产生悬垂指针问题代码也更干净。这道题我前后用不同语言写过很多版本最后只要涉及链表头节点不确定的场景我第一反应都是“先放一个栈上的dummy”。希望这个习惯也能变成你的默认选项。