链表归并排序这个话题，我前前后后写过不下五遍——大学用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->4，mid是节点2，right = 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而不是NULL：
class 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 |
| 单节点 | 5 | 5 |
| 双节点正序 | 1->2 | 1->2 |
| 双节点逆序 | 2->1 | 1->2 |
| 已经有序 | 1->2->3->4 | 1->2->3->4 |
| 完全逆序 | 4->3->2->1 | 1->2->3->4 |
| 含重复值 | 3->1->3->2 | 1->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个节点的完整过程，画清楚每一层的指针状态，再去写代码，基本一次就能过。这篇文章里的递归版、迭代版和排查表都是我自己踩坑后沉淀下来的东西，可以直接拿去用。顺手再提一句：如果链表归并排序能一次写对，你再去练逆置链表、两个有序链表求差集这类题目，会发现指针操作的思路一下子通了很多。先把这个基础打牢，后面的路会顺很多。
