链表归并排序这个话题我前前后后写过不下五遍——大学用C语言在数据结构课上写过一遍工作后在业务系统里处理内存对象链表又写过一遍最近带新人讲链表操作发现几乎每个人都会在同一个地方卡住。表面看它只是一个排序算法实际上是链表遍历、切分、断裂、重接、插入全套基本功的一次综合考试。这篇文章我把自己的完整路线整理出来先从原理上说明为什么链表排序几乎默认选归并再把找中间节点和合并两条有序链表这两个核心子问题拆开讲透最后给出C、Python、Java版本的完整可运行代码、测试用例以及我实际踩过的那些坑。刚学完单链表基础想进阶的读者还有准备面试、刷题的同学都可以直接对照着写。1. 为什么链表的排序绕不开归并排序1.1 数组快排的思路换到链表上处处别扭大概每个人学排序都是从数组开始的。快排在数组上快核心原因是数组支持O(1)随机访问你随手就能拿到中间位置的元素partition时左右指针来回交换也只是在内存连续的区域里做下标运算。链表完全没有这个便利要访问第i个节点必须从head开始一步步走过去。也就是说快排每一次“找基准、分组”都要在链表上做大量的从头遍历性能直接打折扣。就算你用三数取中、尾递归这些优化也补不回随机访问缺失带来的损失。另一个容易被忽略的问题是快排不稳定稳定性在有些业务场景里是要付出额外成本才能弥补的。换到归并排序情况就反过来了。它天生只需要两种操作把一条链表从中间切开以及把两条有序链表合并。这两种操作都只需要顺序遍历和指针重接不需要任何随机访问能力。它就像为单链表量身定做的排序方案。我自己的感觉是学过数组排序后再来看链表归并最需要调整的就是思维模式别再想“交换元素”改想“拆开再按顺序接回去”。1.2 归并排序和单链表在结构上是“同频”的先说复杂度。无论数组还是链表归并排序时间都是稳定的O(n log n)而且是稳定排序相同关键字的元素相对顺序不会被破坏。空间上链表版归并只需要O(1)的额外节点空间递归的调用栈开销另算因为我们合并时只是在原地改next指针不需要像数组归并那样开辟一块临时数组。这一点在很多对内存敏感的场景里非常关键尤其是嵌入式环境下链表节点本身可能放在内存池里额外分配大块数组往往不可接受。我常用一个生活化的类比来解释这种契合度数组像一排列好号码的储物柜你想拿哪个柜子里的东西直接走过去就行链表像一条排队的长队伍你只能从队头挨个往后辨认。归并排序做的事情其实很简单就是从队伍中间划一刀变成两队然后两队的人按个头顺序重新排好。全程不需要跳着看只需要一个一个往后走这和队伍的天然结构是一致的。很多人学这个算法时觉得难是因为脑子里还带着“数组下标”的惯性一旦把模型切换成“队伍”归并排序的逻辑反而非常直白。1.3 横向对比为什么不能是其他排序这里给出一张我做过小规模实验后总结的表列的是几种常见排序算法用在单链表上的实际感受排序算法平均时间复杂度稳定性单链表适配度主要问题插入排序O(n²)稳定中链表上实现直观但数据量一大就慢冒泡排序O(n²)稳定低交换节点或交换值都很别扭基本只有教学意义快速排序O(n log n)不稳定低依赖随机访问链表的partition要反复遍历堆排序O(n log n)不稳定低建堆过程几乎离不开数组下标单链表上实现等于硬拗归并排序O(n log n)稳定高需要会找中点和合并但这两个技能本来就是链表基本功网上也能看到链表的快速排序实现思路是把链表拆成小于、等于、大于三条链表再拼接回来能用但代码绕而且同样要面对递归深度和稳定性问题。结论其实很简单如果你要在单链表上实现一个兼顾时间、稳定性和代码复杂度的大规模排序归并排序基本是唯一不会让自己难受的选择。LeetCode 148和各类数据结构实验里基于链表的排序默认答案基本都是它。2. 拆开看找中点和合并两条有序链表2.1 快慢指针找中间节点差一步可能切歪归并排序的第一步是分治分治就得知道中点在哪。单链表里“求中点”的标准做法是快慢指针慢指针每次走一步快指针每次走两步快指针到链表尾时慢指针正好在中间附近。Node *getMiddle(Node *head) { if (head NULL || head-next NULL) { return head; } Node *slow head; Node *fast head-next; while (fast ! NULL fast-next ! NULL) { slow slow-next; fast fast-next-next; } return slow; }这里有个很多人没注意到的细节初始时我把fast初始化为head-next而不是head。原因是让长度为偶数的链表取到“左中位”而不是“右中位”。比如链表1-2-3-4长度是4我们希望切成1-2和3-4也就是mid是节点2。如果fast初始化为head循环结束后slow会停在节点3切出来就是1-2-3和4这种严重失衡的两段。归并排序理论上能接受不平衡切分但追求平衡切分可以让递归深度更稳定地保持在O(log n)。奇数长度链表用两种初始化结果一样偶数长度就会出现差别。这个one-off错误也是后面各种诡异死循环的高发源头之一。2.2 合并两条有序链表空头节点是省心写法第二个核心操作是merge。两条已经排好序的链表从头开始比较谁小谁就先接到结果链表尾部。关键难点在开头结果链表第一个节点到底是左链表的头还是右链表的头比较之前是未知的。如果不用技巧常见写法是先if判断谁小把第一个节点单独处理再进循环。那种写法容易漏分支也难看。我推荐用“空头节点”dummy head技巧先在栈上创建一个临时节点让它的next指向真正的结果链表头合并过程中统一用tail-next 较小节点最后返回dummy.next就行。Node *merge(Node *left, Node *right) { Node dummy; dummy.next NULL; Node *tail dummy; while (left ! NULL right ! NULL) { if (left-data right-data) { tail-next left; left left-next; } else { tail-next right; right right-next; } tail tail-next; } if (left ! NULL) { tail-next left; } if (right ! NULL) { tail-next right; } return dummy.next; }注意比较条件用的是而不是。这保证了当两个节点值相等时优先取左链表的节点归并排序因此才是稳定的。如果这里写成相等的元素会优先取右链表稳定性就被破坏了。合并的过程说白了就是反复把两个候选头节点中较小的那个“接”到尾巴后面本质上也是链表插入操作的一种特殊形态——每轮循环只做一次O(1)的插入。很多人把“合并有序链表”和“排序”当成两件事其实练好了合并离写出归并排序就只剩一个分治框架了。2.3 切完必须“斩断”这一步决定递归能不能停这是我认为整个链表归并排序里最重要的一个细节也是新手出错率最高的一步找完中点后必须让mid-next NULL把左右两半真正断开。如果不做这一步会发生什么假设链表是1-2-3-4mid是节点2right mid-next指向节点3。但我们没把mid-next置空左半段head到mid这一段虽然在逻辑上是“前半”实际上节点2的next仍然指向节点3整个链表还是完整的一条。对左半段递归时它处理的是完整的1-2-3-4对右半段递归时它处理的又是3-4。两条递归分支操作的是重叠的链表结果就是排序函数永远无法把问题规模缩小到基础情形轻则排序结果错误重则直接栈溢出或形成环。我调试过很多学生的代码最典型的现象就是程序“看起来没反应”加日志才发现递归一直在一个不缩小的子链表里打转。所以我的习惯是写完getMiddle之后紧接着就写一行mid-next NULL并且把这两行当作一个不可分割的组合动作来记忆——找中点、断开、递归三位一体。3. 完整实现C语言为主Python/Java对照3.1 先搭好地基节点定义和基础辅助函数链表归并排序的代码不长但依赖的辅助函数不少建节点、尾插、打印。很多学校的数据结构实验会要求先做“单链表的基本操作实验”其实就是把这些函数写熟。这里给出一个可以直接运行的C版本。#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node; Node *createNode(int data) { Node *node (Node *)malloc(sizeof(Node)); node-data data; node-next NULL; return node; } void append(Node **head, int data) { Node *node createNode(data); if (*head NULL) { *head node; return; } Node *cur *head; while (cur-next ! NULL) { cur cur-next; } cur-next node; } void printList(Node *head) { while (head ! NULL) { printf(%d - , head-data); head head-next; } printf(NULL\n); }这里的append是O(n)的尾插每次建测试数据时总复杂度是O(n²)数据量不大无所谓。如果测试大规模数据建议先存数组再批量建链表或者用一个tail指针维护尾部。顺便说一句如果想系统练一遍链表基础操作洛谷B3631是一道单向链表模拟题很适合先刷一遍再回来写归并手感会顺很多。3.2 递归版归并排序核心代码逐行说明把前面两个子问题拼起来就是这个算法的主体递归版归并排序。Node *mergeSort(Node *head) { if (head NULL || head-next NULL) { return head; } Node *mid getMiddle(head); Node *right mid-next; mid-next NULL; Node *leftSorted mergeSort(head); Node *rightSorted mergeSort(right); return merge(leftSorted, rightSorted); }递归的基准情形是空链表或只有一个节点这两种链表天然有序直接返回。否则找中点、断开分别对左半段和右半段递归排序最后把两个有序段合并。有个容易混淆的点左边传入的仍然是head因为head节点本身没变右边传入的是mid-next。所以函数签名不需要“范围参数”返回值是排序后的新头节点。这也是链表归并和数组归并的一个很大区别数组归并要传区间下标链表归并只需要传头指针因为链表节点本身携带了后续信息。在主函数里测试一下int main() { Node *head NULL; int arr[] {5, 2, 9, 1, 7, 6, 3}; for (int i 0; i 7; i) { append(head, arr[i]); } printf(原始链表: ); printList(head); head mergeSort(head); printf(排序后: ); printList(head); return 0; }用5-2-9-1-7-6-3举例第一轮getMiddle切出来的是以第四个节点1为中点的两段左半段5-2-9-1右半段7-6-3。然后左右各自递归左半段再切成5-2和9-1再切、再合并直到每个子链表长度不超过1。回溯时一步步把有序小段合并成有序大段最后得到1-2-3-5-6-7-9。整个过程可以浓缩成一句话先拆到不能再拆再边合并边排序。3.3 Python和Java实现的差异点C语言版的逻辑一懂Python版基本就是换皮最大差别是Python用None而不是NULLclass Node: def __init__(self, data): self.data data self.next None def get_middle(head): if not head or not head.next: return head slow, fast head, head.next while fast and fast.next: slow slow.next fast fast.next.next return slow def merge(left, right): dummy Node(0) tail dummy while left and right: if left.data right.data: tail.next left left left.next else: tail.next right right right.next tail tail.next tail.next left or right return dummy.next def merge_sort(head): if not head or not head.next: return head mid get_middle(head) right mid.next mid.next None left_sorted merge_sort(head) right_sorted merge_sort(right) return merge(left_sorted, right_sorted)Java版则要注意在类里定义ListNode节点比如LeetCode 148里给的是val和next两个字段。核心代码几乎一致只是把方法放进类里改一下类型名和空判断写法。如果你搜“归并排序原理java”很多题解写的也是同样的分治思路。我的看法是语言之间的差异不用太纠结逻辑吃透了换语言只是语法翻译问题反倒是递归里的“断开”动作换到哪个语言都不能省。3.4 测试用例与边界情况验证我对自己写的东西有个习惯写完代码先跑一遍边界用例再跑正常用例。链表归并排序至少要覆盖下面这些场景用例输入期望输出空链表NULL返回NULL单节点55双节点正序1-21-2双节点逆序2-11-2已经有序1-2-3-41-2-3-4完全逆序4-3-2-11-2-3-4含重复值3-1-3-21-2-3-3包含负数-3-5--1-0-3--1-0-5排序前先打印链表长度排序后再打印一次长度两次数值必须一致。这是一个非常便宜的完整性校验归并排序只是重接指针不应该改变节点数量。如果前后长度不一致几乎可以断定是merge或断开阶段把链表接丢了。4. 实操中我遇到过的几个诡异问题4.1 一排序就栈溢出先检查是不是没断链新手最常见的现象是小链表比如三五个节点排序正常一旦给到几千个节点程序直接崩溃报栈溢出。很多人第一反应是“递归太深了”但其实归并排序递归深度是O(log n)几千个节点深度也就十几层根本不该溢出。真正的根因往往就是没断链导致递归退化成了O(n)深度。排查办法很简单在mergeSort里打印mid-data如果发现递归几次后mid永远是同一个节点说明子链表没有被真正切开。把mid-next NULL加上问题立刻消失。4.2 输入链表带环快慢指针永远跑不到头还有一种情况不是归并写错了而是输入数据本身有问题。如果测试时意外拿到链表尾节点的next指向了链表中某个节点形成环getMiddle里的fast永远等不到NULL程序会一直循环。这种时候先别改排序逻辑应该先做环检测。常见的判断方法是快慢指针相遇法两个指针分别走一步和两步如果它们相遇说明有环。知道有环之后一种做法是先定位环入口并解环再排序另一种做法是明确业务语义——如果这个链表本来就应该是一个循环单链表那就不该用普通排序流程需要单独处理这个我在第5节详细说。4.3 排序后节点变少或链表断成两截另一个高频bug是排序结果里节点数量变少或者打印时中间出现断掉的情况。我排查过几次原因几乎都出在merge函数结尾一个链表先被取空之后剩下的那段要整段接到tail后面。如果你写的是循环里逐个节点搬运就容易把剩余链表的第一节点处理完之后忘记把它后续的节点完整接上。正确写法就是上面代码里的tail-next left或right整段挂接不要逐个搬运。判断断链最简单的方法还是打印长度以及从排序后头节点开始数一遍节点数量数不完整就说明中间某个next丢了。4.4 一份常见问题速查表把我在实际开发、教学和面试辅导里遇到的高频问题整理成一张表方便排查时对照症状可能原因排查手段递归卡死或栈溢出mid-next没有断开递归未收敛打印mid-data补上断链fast指针走不到头链表有环先用环检测解环后再排序排序结果节点数变少merge尾部挂接漏节点排序前后各打印一次长度偶长链表切分不均衡fast初始化为head把fast改成head-next等值元素顺序被改变merge用了而不是改成保证稳定性大链表排序极慢建链表用O(n²)尾插用数组或tail指针批量构建5. 延伸循环链表与自底向上迭代版5.1 循环链表单循环链表怎么做归并排序热词里出现“循环单链表”“单循环链表”说明不少人在研究这个方向。循环链表的尾节点不再指向NULL而是指回头节点。标准的归并排序依赖NULL作为遍历终止条件直接用在循环链表上会死循环。实际工程里我的做法是“先解环再排序排完再成环”。第一步遍历循环链表找到尾节点。所谓尾节点就是cur-next head的那个节点。把它的next置为NULL链表从环形退化成普通单链表。第二步跑前面第3节的递归版归并排序。第三步排序完成后找到新的尾节点把它的next指回排序后的头节点重新成环。注意排序后的头节点可能已经变了比如原头节点恰好是最大值所以第三步里不能再用原来的head指针必须用mergeSort的返回值作为新的头。这个流程的好处是复用了所有已经验证过的代码不需要专门为循环链表重写一套getMiddle和merge。唯一要注意的是解环时如果链表只有一个节点它的next同时指向自己判断逻辑要兼容这种情况。5.2 自底向上迭代版不用递归栈嵌入式场景更友好递归版虽然代码简洁但每一层递归都要占用调用栈。在嵌入式环境里栈空间往往很紧张递归深度可能成为隐患。这时候适合用自底向上的迭代版思路和数组归并的迭代版完全一致先把每个节点看成大小为1的有序块两两合并得到大小为2的有序块再两两合并得到大小为4的有序块直到整条链表有序。Node *mergeSortIterative(Node *head) { if (head NULL || head-next NULL) { return head; } int len 0; for (Node *p head; p ! NULL; p p-next) { len; } Node dummy; dummy.next head; for (int step 1; step len; step 1) { Node *prev dummy; Node *cur dummy.next; while (cur ! NULL) { Node *left cur; Node *leftTail left; for (int i 1; i step leftTail-next ! NULL; i) { leftTail leftTail-next; } Node *right leftTail-next; if (right NULL) { prev-next left; break; } leftTail-next NULL; Node *rightTail right; for (int i 1; i step rightTail-next ! NULL; i) { rightTail rightTail-next; } Node *nextHead rightTail-next; rightTail-next NULL; Node *merged merge(left, right); prev-next merged; while (prev-next ! NULL) { prev prev-next; } cur nextHead; } } return dummy.next; }核心逻辑是外层循环控制“块大小”step从1开始每轮翻倍内层循环每次取两个长度为step的块分别切断、合并再接到已排序的结果链表尾部。这里用dummy作为每一轮的链头占位是为了让prev-next的挂接逻辑统一也避免讨论“头节点被换掉”的特例。这个版本完全不使用额外栈空间只用了几个局部指针空间开销是O(1)在嵌入式链表代码示例这种场景下比递归版更稳。缺点也很明显代码比递归版长边界条件多第一次写容易在“取块”和“接回”两个环节出错。我的建议是先把递归版吃透、调通再尝试迭代版并且用同一套测试用例去验证两版结果一致。我实际用下来的体会是链表归并排序真正考验人的地方从来不是背出这段代码而是能不能把找中点、断链、合并这三件事在纸上画清楚再动手写。带新人的时候我一直坚持让他们先拿小纸片模拟一遍4个节点的完整过程画清楚每一层的指针状态再去写代码基本一次就能过。这篇文章里的递归版、迭代版和排查表都是我自己踩坑后沉淀下来的东西可以直接拿去用。顺手再提一句如果链表归并排序能一次写对你再去练逆置链表、两个有序链表求差集这类题目会发现指针操作的思路一下子通了很多。先把这个基础打牢后面的路会顺很多。
