递归、链表、归并排序这三个词放到一起时往往就是算法学习路上的一道分水岭。数组排序写顺手之后一碰到链表很多人第一反应是“那就复制到数组里排完再重建链表”这种思路不能说错但丢掉了链表擅长的东西——原地重排指针。归并排序恰好只看节点的 next 和数值比较天生就跟链表的内存结构合拍递归又是链表这个递归结构的自然表达方式。这篇文章我从自己写这段代码时的思考和踩坑出发把为什么选归并、递归框架怎么搭、合并函数怎么写、自底向上又怎么优化全部讲透适合刚学数据结构的学生、准备算法面试的求职者以及工作中实际要处理链表排序的工程师直接参考。1. 为什么链表排序绕不开归并1.1 链表的“内存性格”决定算法取舍数组在内存里是一整块连续空间按下标随机访问只需要 O(1) 的时间。这个特性让快排、堆排这类依赖“跳到某个位置”的算法如鱼得水。链表不同节点散落在内存里访问第 k 个节点必须从头走 k 步随机访问是 O(n)。这意味着任何基于下标跳跃的经典做法都不能直接套到链表上。归并排序的核心操作只有两个把序列对半切以及把两个已经有序的序列按大小合并。切分不依赖随机访问只要会数长度就能做合并本质上是从两个链表的头部依次把较小节点拎出来走一遍顺序遍历。这刚好把链表唯一方便的访问方式——顺序遍历——用到了极致。所以说归并排序不是“也能用”于链表而是目前综合来看最契合链表结构的排序方案。这一点我最早没想明白。我刚开始尝试用类似快排的思路处理链表选一个基准值然后把链表拆成小于、等于、大于三段再递归排序。算法本身也能工作但每一轮 partition 都要完整遍历链表而不像数组那样可以靠首尾指针快速收敛实际常数大很多。递归效率是 O(n log n)但递归树每一层的常数比归并大实测数据一大就慢下来而且快排不稳定排序后相等元素的相对顺序就找不回来了。1.2 插入、堆排与快排在链表上的不同结局插入排序在链表上反而比数组更顺手因为链表插入节点只需要改指针不用像数组那样搬移元素。但它的时间复杂度是 O(n^2)。如果链表节点数达到几千上万排序时间肉眼可见地上涨。一两个无序节点组成的近似有序链表插入排序狠好用但一般数据分布下不敢拿它撑场面。堆排需要拿到第 k 个节点的左右孩子进行下沉操作数组靠下标直接算链表得从头遍历才能找到对应节点一次下沉就可能是 O(n) 的额外代价堆化整体变成 O(n^2)。这个方案不用考虑了。快排的问题在于 partition 过程和随机访问强绑定。数组快排的经典写法需要两个下标一头一尾交替扫描链表没有“下标”只有“指针”。把链表转成数组快排再转回来确实能解决但空间复杂度 O(n)还要额外做一遍节点拷贝和重建跟归并比没有任何优势。1.3 各排序算法在链表上的表现对比算法平均时间最好时间最坏时间额外空间稳定性链表适配度直接插入排序O(n^2)O(n)O(n^2)O(1)稳定常数小适合近似有序快排链表版O(n log n)O(n log n)O(n^2)O(log n)不稳定常数偏大边界繁琐堆排O(n log n)O(n log n)O(n^2)O(1)不稳定无法高效定位子节点归并排序递归O(n log n)O(n log n)O(n log n)O(log n)稳定完全适配常数小从这张表可以直观看到归并在链表场景下几乎没有短板。它的时间稳定在最坏 O(n log n)不依赖输入的初始有序程度额外空间主要来自递归栈log n 级别稳定这一条在真实业务里往往很关键比如链表节点里除了排序键还有很多字段不该因为排序把字段顺序搞乱。2. 递归框架拆分、排序、合并2.1 递归函数的三段式结构把归并排序用递归写出来对链表来说其实非常顺。链表本身就是递归结构一个节点指向下一个节点下一个节点又指向下一个这种“自己包含自己模式”跟递归在语义上是一致的。递归函数 sortList 只需要做三件事拆找到链表中点把链表切成左右两段。递归左边排序右边排序各自返回有序链表的头指针。合把两个有序链表合并成一个完整有序链表并返回新头。用伪代码表达就是sortList(head): 如果 head 为空或 head.next 为空 返回 head mid 找中点(head) right sortList(mid.next) mid.next null # 关键把左右两段彻底断开 left sortList(head) 返回 merge(left, right)你可能会疑惑为什么 mid.next 要置为 null因为 merge 函数必须知道“我的链表从哪里结束”。链表的结束标志就是 next 为 null。如果不把左半段的尾巴截断merge 一旦遍历到原来的后半段就会把整条链连回去结果不是合并而是直接跑进一段未排序的区域最终整个排序彻底乱套。这个置空操作是链表归并和数组归并最大的区别之一。数组归并靠下标边界控制范围链表必须靠指针的 null 来控制范围。另外注意递归调用是“先右后左”还是“先左后右”并不重要因为左右互不依赖。真正重要的是在递归之前就把 mid.next 截断。如果你先对右半段做递归再回来截断理论上也能跑通因为 mid 和 mid.next 始终还在内存里但逻辑上不清爽容易在后面合并时搞混左右链表的边界。我建议先把边界切开再进入递归让每一步递归都处理一个结构完整、独立成链的子问题。2.2 快慢指针找中点的原理与边界找单链表的中点常规做法是快慢指针。让 slow 一次走一步fast 一次走两步。fast 到达链表末尾时slow 正好停在中间位置。Node* findMiddle(Node* head) { if (head NULL) { return NULL; } Node* slow head; Node* fast head; while (fast-next ! NULL fast-next-next ! NULL) { slow slow-next; fast fast-next-next; } return slow; }这里我选择 while (fast-next ! NULL fast-next-next ! NULL)而不是很多人写的 while (fast ! NULL fast-next ! NULL)。两种写法都能用区别在于 slow 停在中点的哪一侧。我用的条件会让 slow 停在偏左侧的中点也就是把链表切成两段时左段不小于右段链表长度 1不进循环slow 停在唯一节点。链表长度 2fast-next 存在但 fast-next-next 不存在slow 停在第一个节点左段 1 个、右段 1 个。链表长度 3进一次循环slow 到第二个节点左段 2 个、右段 1 个。链表长度 4进一次循环slow 到第二个节点左段 2 个、右段 2 个。这种“下取整”的切分方式可以保证递归过程中任何非空链都能被拆成至少各有一个节点的两段不会出现右段为空导致递归无法收敛的情况。如果你用 while (fast ! NULL fast-next ! NULL)slow 会停在偏右的中点上对偶数长度链会得到左段 2 个、右段 2 个但处理空链表和长度 1 的链表时循环条件会对 fast 先做一次判断代码略复杂一点。两种写法都能实现归并排序选一种自己能讲清楚的就行。还有一个细节值得注意这个函数只是在“找中点”并不负责切分。真正的切分发生在 sortList 里找到中点后把 mid-next 保存起来作为右段头节点再把 mid-next 置空。这样拆分和排序两个职责分离代码更好读调试时也更容易定位问题。2.3 递归出口为什么是“空或单节点”递归出口就一句话if (head NULL || head-next NULL) return head。这个判断包含两种情形。head 为 NULL说明调用方传来了一个空链表不需要排序。head-next 为 NULL说明当前链表只有一个节点单个节点天然有序也不用排序。这个出口位于归并排序递归过程的最底部是“分而治之”里的“治到底”的标志。写这段代码最大的禁忌是想当然地把空链表情况漏掉。如果你只写 if (head-next NULL)一旦 head 是 NULL访问 head-next 直接就是空指针异常。链表排序的递归会一路拆到只剩一个节点的链空指针判断不仅仅是为了防御调用方不传空链更是递归过程中必需的安全网。你甚至可以把出口简化为 if (head NULL || head-next NULL)这个习惯我一直保留省去很多边界漏判的问题。3. 合并两个有序链表细节决定成败3.1 迭代合并法哨兵节点省心省事合并操作的核心任务是把两个各自有序的链表按大小穿插成一个有序链表。虽然归并排序整体用了递归但真正的“治”我建议用迭代来实现。迭代合并的空间复杂度 O(1)而递归合并的空间复杂度 O(n)容易在链表较长时拖累整体。Node* merge(Node* l1, Node* l2) { Node dummy; // 哨兵节点 Node* cur dummy; dummy.next NULL; while (l1 ! NULL l2 ! NULL) { if (l1-val l2-val) { cur-next l1; l1 l1-next; } else { cur-next l2; l2 l2-next; } cur cur-next; } if (l1 ! NULL) { cur-next l1; } if (l2 ! NULL) { cur-next l2; } return dummy.next; }这里 dummy 是一个栈上的哨兵节点不是正式节点它的作用只有一个给 cur 提供一个稳定的起点。如果不使用哨兵就得单独处理“合并后的第一个节点到底取自 l1 还是 l2”的问题代码会多出一段 if-else。哨兵写法让每次循环都统一处理返回时直接拿 dummy.next 就行。合并过程中我没有新建任何节点只是不断修改已有节点的 next 指针。这一点非常重要。很多初学者习惯“照抄数组归并”先 new 一排新节点再赋值结果排序前后的节点身份全变了。如果你排序后还需要访问节点中的其他字段或者外部还有别的指针指向这些节点复制重建会把整个数据结构弄得一团糟。链表归并的优雅之处就在于通过指针拼接完成任务不申请额外的节点内存。3.2 递归合并法直观但有额外代价迭代版 merge 已经很简洁了但递归版更短思路也更“声明式”Node* mergeRecursive(Node* l1, Node* l2) { if (l1 NULL) { return l2; } if (l2 NULL) { return l1; } if (l1-val l2-val) { l1-next mergeRecursive(l1-next, l2); return l1; } else { l2-next mergeRecursive(l1, l2-next); return l2; } }这段代码读起来非常顺如果一条链空了返回另一条否则取较小值所在节点做头然后递归合并剩下部分。但代价是每一次递归都会消耗一层调用栈。合并长度为 n 的链最坏情况下递归 n 层空间 O(n)而且尾递归优化不是所有编译器对链式递归都能做到的。我在最终的 sortList 里用的是迭代 merge因为整个排序的空间复杂度只保留快慢指针和递归栈的 O(log n)更均衡。3.3 合并操作中必须守住的三个底线第一两条输入链必须是被截断过的独立链表。merge 通过判断 l1 和 l2 是否为 NULL 来结束循环如果其中一条链的尾巴连到了另一段未排序的链表merge 会一直遍历到错误位置或形成环。所以在 sortList 中把 mid-next 置空是硬性前提。第二值相等时取 l1也就是左边链表的节点。这样归并排序就是稳定排序。如果业务场景不要求稳定性取 l1 或 l2 无所谓但保持稳定不需要额外代价养成取左边的习惯没坏处。第三合并完成后新链表的尾节点必须是 NULL。两条输入链尾节点本来就是 NULL拼接过程中不会引入新的尾节点所以这一点只要输入正确就能自动保证。如果你手动改成通过 while(l1) 循环逐个接节点的写法反而容易漏掉最后一段的尾部多加代码还容易出错。4. 完整实现可直接复制的C语言代码4.1 代码整体布局与环境说明下面是一段完整可运行的 C 语言实现。用 C 写链表的好处是节点和指针的关系无处躲藏每一步操作都明明白白对理解原理帮助最大。换成别的语言思路完全一样只是把指针操作换成引用或对象赋值。#include stdio.h #include stdlib.h typedef struct Node { int val; struct Node* next; } Node; Node* findMiddle(Node* head) { if (head NULL) { return NULL; } Node* slow head; Node* fast head; while (fast-next ! NULL fast-next-next ! NULL) { slow slow-next; fast fast-next-next; } return slow; } Node* merge(Node* l1, Node* l2) { Node dummy; Node* cur dummy; dummy.next NULL; while (l1 ! NULL l2 ! NULL) { if (l1-val l2-val) { cur-next l1; l1 l1-next; } else { cur-next l2; l2 l2-next; } cur cur-next; } if (l1 ! NULL) { cur-next l1; } if (l2 ! NULL) { cur-next l2; } return dummy.next; } Node* sortList(Node* head) { if (head NULL || head-next NULL) { return head; } Node* mid findMiddle(head); Node* rightHead mid-next; mid-next NULL; Node* leftSorted sortList(head); Node* rightSorted sortList(rightHead); return merge(leftSorted, rightSorted); } Node* append(Node* head, int val) { Node* newNode (Node*)malloc(sizeof(Node)); newNode-val val; newNode-next NULL; if (head NULL) { return newNode; } Node* cur head; while (cur-next ! NULL) { cur cur-next; } cur-next newNode; return head; } void printList(Node* head) { while (head ! NULL) { printf(%d , head-val); head head-next; } printf(\n); } void freeList(Node* head) { while (head ! NULL) { Node* tmp head-next; free(head); head tmp; } } int main() { Node* head NULL; int arr[] {4, 2, 1, 3, 5, 9, 6, 8, 7, 0, 4}; int n sizeof(arr) / sizeof(arr[0]); for (int i 0; i n; i) { head append(head, arr[i]); } printf(Before: ); printList(head); head sortList(head); printf(After: ); printList(head); freeList(head); return 0; }编译运行之后输出是Before: 4 2 1 3 5 9 6 8 7 0 4 After: 0 1 2 3 4 4 5 6 7 8 9可以看到重复元素 4 出现了两次排序后连续在一起。这里我用 val 作为排序键接下来我会直接用 val 这个说法说明排序依据。4.2 复杂度分析时间、空间、稳定性时间复杂度的推导是标准的递归展开。每层归并要遍历整个链表一次长度为 n递归树有 log n 层所以总时间 O(n log n)。归并排序不像快排不存在最坏情况任何输入顺序下都比较稳定的 n log n 次比较。空间上递归栈的深度是 log n因为每次拆分都把问题规模减半。迭代 merge 不使用额外空间快慢指针只用常数个变量。所以整体额外空间 O(log n)。这比数组归并的 O(n) 辅助空间好得多也是链表归并的重要优势。稳定性方面我在 merge 里用 而不是 相等时取左链节点保证相等元素的原始顺序不被打乱。这对排序对象较复杂时很有意义比如按成绩排序的学生链表里成绩相同的学生相对顺序不应该被改变。4.3 测试样例与运行验证我习惯在写完排序代码后准备几组特殊输入做验证空链表head 为 NULL应该直接返回 NULL。单节点链表排序前后不变。两个节点逆序输入比如 {2, 1}排序后 {1, 2}。全相等值比如 {5,5,5}排序后不变同时验证稳定性不会造成死循环。随机大数组可以选择构造 1 万个随机节点排序后检查是否严格递增。上面代码里我故意把数组设计成包含重复值和逆序片段一次跑通后能覆盖绝大多数常规情况。实际开发中如果链表节点数大到千万级别自底向上的实现会更稳这部分下面单开一章讲。5. 高频踩坑快慢指针、截断和调试实录5.1 快慢指针的边界条件别再死在while里快慢指针是链表归并里最容易出边界问题的地方。我见过最多的情况是把 while 条件写成 while (fast ! NULL fast-next ! NULL) 却忘了在循环里对 fast 做空指针保护。实际上这个条件本身不会空指针但 fast 会停在最后一个节点或者 NULLslow 的位置可能偏向右侧中点。对于归并排序来说偏左偏右都能正常工作怕的是写混之后在某些分支上 fast-next 为空继续访问 fast-next-next 直接崩掉。我把两种写法的区别整理成表方便对照循环条件slow 指向位置处理空链方式fast-next fast-next-next偏左中点不需要额外判 fast 为空fast fast-next偏右中点需要额外处理 fast 为空的情况我用第一种最主要的考虑是它能保证拆出来的左段长度不小于右段递归的左右子树规模相对均衡代码也少写一个 fast 判空。你只要记住一个原则循环条件里用的表达式决定了你会不会访问空指针。写完代码后拿长度为 1、2、3、4 的链表在心里跑一遍是排查边界条件最廉价的方法。5.2 截断不彻底会导致合并成环递归归并里第二高频的问题是截断时机不对。我最初写 sortList 时先递归排序右半段再设置 mid-next NULL看起来只是顺序换了一下结果在 merge 时出现了链表成环。原因很简单右半段排序返回后它的尾部并没有指向 NULL而是依然连着原链表后面的部分。递归处理右半段时右半段内部的递归会截断它自己的段但返回给上层的整段右链尾节点可能指向一个已经被排序过的节点这个节点可能恰恰属于左半段于是在 merge 拼接时cur-next 接上了环。解决方法是把截断动作放在递归调用之前像第 4 节代码那样。先 mid-next NULL把左右两段彻底焊死成独立链表再进行递归。这样每一层拿到的输入链都是一个结构完整、尾节点干净的链merge 才能安心地依赖 NULL 判定结束。这个坑我用了一个笨办法才定位到。当时结果是排序后链表长度不对遍历的时候有些节点重复出现产生了死循环。排查方法很简单在 merge 开头打印 l1 和 l2 的头节点值在 merge 内部每走一步打印当前拼接的节点值看哪里开始出现重复段。最终定位到是截断时机的问题。5.3 画图调试法指针问题别靠“看代码”链表代码调试有个经验别死盯着代码看画图比盯代码有效一万倍。一次面对三四个节点、每个节点有 val 和 next 两个字段你在脑子里模拟指针变化很容易乱。我的做法是把每个节点画成一个小方框val 写在框里next 画成箭头然后用不同颜色的笔标记 slow、fast、left、right 这四个指针。每执行一次循环就擦掉重画一次。画两三轮下来你会发现之前想不通的指针顺序问题其实只是“某个指针指到了自己”或者“原来某段链没断开”。我在给别人讲链表归并时也推荐这种画图法尤其是快慢指针和 merge 的部分。这不是效率低而是链表这种链式结构本来就特别适合用图示来推理。等你把几组典型输入画熟练了写代码时脑海中自然就有画面边界条件也不容易漏。5.4 内存与性能层面的工程提醒用 C 写链表还得考虑内存释放问题。sortList 本身不会新增节点所以不会造成内存泄漏。真正需要小心的是你在构造测试链表时 new 出来的节点测试结束要释放。第 4 节代码里的 freeList 就是干这个的。如果你在 merge 里不小心 new 了节点不仅泄漏内存还会让原链表节点被丢弃后续访问字段会出错。性能上还有一个容易被忽略的点merge 是频繁调用的大头函数内层 while 循环每执行一次就做一次节点拼接常数越小越好。用哨兵节点和直接字符串指针操作已经是最简形式不要再在循环里做 malloc、free 或者冗余的临时变量复制。链表归并的时间复杂度虽然固定但常数项的大小直接决定了实际干活快不快。6. 递归之外的进阶自底向上归并排序6.1 递归的栈代价与替代思路递归实现代码优美、逻辑清晰但它有一个天然的上限递归栈深度。虽然链表归并的递归深度是 log n1 亿节点的链表只需要 27 层递归理论上完全没有问题但在某些受限环境里比如嵌入式设备、递归栈被压得很小的系统或者你对调用栈深度有严格约束的实时任务递归还是会成为顾虑。自底向上的归并排序可以做到 O(1) 额外空间。思路和数组的自底向上归并一致先把链表看成 n 个长度为 1 的有序子链两两合并成 n/2 个长度为 2 的有序子链再两两合并成长度为 4 的子链直到整个链表合成一个有序链。区别在于数组可以用下标按步长精确切段链表要通过指针一步步走相应步数来切段。6.2 自底向上的切段合并实现核心是写一个 split 函数给定一段链表和一个长度 size它从链头走 size 步把这段切下来并返回后半段的新头。然后用两层循环外层控制子链长度 size内层从左到右依次切出两个 size 长度的子链合并接到结果链尾部。Node* split(Node* head, int size) { if (head NULL) { return NULL; } for (int i 1; head-next ! NULL i size; i) { head head-next; } Node* rest head-next; head-next NULL; return rest; } Node* sortListIterative(Node* head) { if (head NULL || head-next NULL) { return head; } int len 0; Node* cur head; while (cur ! NULL) { len; cur cur-next; } Node dummy; dummy.next head; for (int size 1; size len; size * 2) { Node* prev dummy; Node* cur dummy.next; while (cur ! NULL) { Node* left cur; Node* right split(left, size); cur split(right, size); prev-next merge(left, right); while (prev-next ! NULL) { prev prev-next; } } } return dummy.next; }这里需要解释几个关键点。split(left, size) 会把 left 的前 size 个节点切下来后半段作为新头返回同时把 left 段末尾置空。如果剩下的节点不足 size 个split 会走走到链表末尾返回 NULL。然后 cur split(right, size) 再去切下一对子链的头。这个“先切两段再切下一段”的顺序保证游标 cur 永远指向尚未处理的剩余链表的头。内层循环结束后prev 会被移动到合并后的链表尾部下一轮处理时从正确的位置继续拼接。dummy 节点在这里的作用是充当总表的头节点让每一轮的第一段合并都能统一挂在虚拟头之后。这段代码的空间复杂度 O(1)时间仍然是 O(n log n)只是常数略大一些因为 split 每次要按 size 步长走指针。6.3 工程场景下的方案选择建议如果你是在算法笔试或技术面试场景优先写递归版。它思路清晰、代码短面试官更容易看懂你的逻辑你也更容易在讲题时把每一步解释清楚。如果你在真实项目里处理超长链表又对额外内存非常敏感自底向上版本是更稳妥的选择。还有一种更日常的做法也值得一提如果链表节点数量不大排序频率不高退化成遍历链表、把键值拷到数组、用库函数排序再按数组顺序重新设置节点值和链接结构有时反而是工程上最快的路子。数组排序经过了高度优化cache 也友好。但这不是“链表排序算法”本身的竞争力只是“偷懒工程学”的权衡。真要考察数据结构功底归并排序不依赖随机访问原地重排指针才是基本功。我个人在实际写链表归并时最深的体会是链表题的关键不在于把代码背下来而在于对“指针指向谁、谁的下一个是谁、谁的尾巴是 NULL”这三件事有画面感。递归归并表面上考的是分治思想实质上考的是你能不能把链表拆成独立子问题再正确地接回去。先用第 4 节的代码跑通再试着去掉注释盲写一遍遇到环、死循环、漏节点的情况就去画图画几次之后你会发现链表归并其实比数组归并更容易理解因为它的“拆分”和“合并”都是物理上可操作的节点拼接不再只是一个虚拟的下标范围。