递归、链表、归并排序，这三个词放到一起时，往往就是算法学习路上的一道分水岭。数组排序写顺手之后，一碰到链表，很多人第一反应是“那就复制到数组里排完再重建链表”，这种思路不能说错，但丢掉了链表擅长的东西——原地重排指针。归并排序恰好只看节点的 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 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 停在唯一节点。
• 链表长度 2：fast->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 会停在最后一个节点或者 NULL，slow 的位置可能偏向右侧中点。对于归并排序来说，偏左偏右都能正常工作，怕的是写混之后在某些分支上 fast->next 为空，继续访问 fast->next->next 直接崩掉。

我把两种写法的区别整理成表，方便对照：

我用第一种最主要的考虑是，它能保证拆出来的左段长度不小于右段，递归的左右子树规模相对均衡，代码也少写一个 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 n，1 亿节点的链表只需要 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 节的代码跑通，再试着去掉注释盲写一遍，遇到环、死循环、漏节点的情况就去画图，画几次之后你会发现链表归并其实比数组归并更容易理解，因为它的“拆分”和“合并”都是物理上可操作的节点拼接，不再只是一个虚拟的下标范围。