刷题刷到链表排序很多人会惯性套数组那套快排结果写着写着发现连中间节点都拿不到直接卡住。BM12 这道「单链表的排序」考察的正是链表场景下怎么把 O(n log n) 的排序跑起来。标准答案就是归并排序——它的合并操作天然适合链表节点间的指针拼接而且不像数组那样需要 O(n) 的额外存储。这篇文章我会从头拆解这道题的完整思路为什么链表排序选归并、快慢指针怎么找中点、有序链表怎么原地合并、递归和迭代两种写法各有什么坑最后再附上调试时踩过的边界问题。不管是面试前突击还是数据结构期末复习都可以拿这篇自检。1. 题目拆解单链表排序为什么首选归并1.1 先搞清题目在考什么题目给的是一个单链表只给头节点要求按升序排序最后返回新链表的头节点。乍一看就是个普通排序题实际考点藏在链表这个数据结构里。单链表最大的特点是没有随机访问能力。数组里拿下标能直接定位到任意位置链表只能一个节点一个节点往后走而且节点还散落在内存各处靠 next 指针串联。这个特点决定了算法选取的边界。先看快速排序。数组版快排的核心是左右两个指针从两端向中间逼近一趟 partition 交换元素。放到链表上右指针没法直接从尾部往前走每次移动都要从头遍历一趟下来时间复杂度退化成 O(n²)。虽然也有“单链表快排”的写法用一个指针做 partition但实现繁琐递归深度不稳定最坏情况依然可能 O(n²)笔试面试里没必要冒这个险。再看堆排序。堆排序在建堆和向下调整时需要根据下标计算父节点、左右孩子节点的位置这是数组的专属能力链表根本没有下标概念。硬做的话还得先把链表转成数组那额外空间就上去了违背了链表省空间的初衷。插入排序倒是能直接在链表上实现逻辑也简单但最坏时间复杂度 O(n²)n 稍大一点就顶不住。筛选一圈下来归并排序几乎是唯一适配链表的高效选择。归并排序的核心操作是“合并两个有序链表”这本质上就是把两条链子按顺序串起来只改 next 指针不需要额外数组。数组上的归并要开临时数组才能合并链表上的归并连这个都省了。这正是归并排序在链表场景下的最大优势。题目里通常还会带一句“空间复杂度 O(1)”这句话其实是在暗示用自底向上的迭代版归并。递归版虽然好写但递归栈深度是 O(log n)严格抠空间复杂度时会被面试官追问。这点等到第三节细讲。1.2 各排序算法在链表上的表现对比排序算法平均时间复杂度空间复杂度稳定性链表上的可操作性归并排序O(n log n)O(1)迭代版稳定很合适本质就是指针拼接快速排序O(n log n)O(log n) 递归栈不稳定不适合缺随机访问堆排序O(n log n)O(1)不稳定很不适合缺下标计算插入排序O(n²)O(1)稳定能实现但 n 大时太慢选择排序O(n²)O(1)不稳定能实现但 n 大时太慢这个表基本能回答“为什么非要用归并”。时间复杂度达标的只有快排、堆排、归并前两个在链表上都有硬伤归并是那个没有明显短板的选项。另外还有稳定性这个隐藏考点。归并排序是稳定排序合并两个有序链表时只要保证值相等时优先取左半段的节点原链表里值相同的节点排序后相对顺序不变。面试官如果追问“两个节点值相同排序后会交换位置吗”答案是不会。如果你在 merge 里把比较符号写成l1-val l2-val那值相等时会优先取右半段稳定性就被破坏了这是个非常容易忽略的细节。2. 归并排序的核心操作拆解2.1 快慢指针找中点归并排序的第一步是分治也就是把链表从中间切开分成左右两半分别排序后再合并。数组可以直接取下标 mid链表只能通过快慢指针找中点。快慢指针的思路很直观慢指针 slow 一次走一步快指针 fast 一次走两步。当 fast 走到链表末尾时slow 正好停在中间位置。这个原理跟跑步套圈差不多fast 的速度是 slow 的两倍同一时间跑出去的距离也是两倍fast 到终点时 slow 自然在路程一半的位置。但实现上有几个细节值得注意。循环条件一般是while (fast ! nullptr fast-next ! nullptr)这个条件要保证 fast 能合法地走两步。如果写成while (fast-next ! nullptr fast ! nullptr)求值顺序反了空链表或单节点链表下会先访问 fast-next 直接崩溃。指针判空永远放在前面。第二个细节是 fast 的初始位置。写成fast head也行但写成fast head-next更稳。区别在于偶数长度的链表假设链表有 4 个节点fast head时慢指针最后停在第三个节点上左半段 2 个节点、右半段 1 个节点不算停靠点fast head-next时慢指针停在第二个节点上切成两段各 2 个节点分治更均衡。第三个细节是断链。找到中点后要记下右半段的头然后把中点节点的 next 置空否则递归或迭代时左右两半还是连在一起的合并过程中很容易形成环。放一段我最常用的找中点逻辑ListNode* slow head; ListNode* fast head-next; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; } ListNode* rightHead slow-next; slow-next nullptr;这段代码执行完后head 到 slow 是左半段rightHead 开始是右半段两段都已经是独立链表。2.2 有序链表的原地合并归并排序的第二个核心操作是把两个有序链表合并成一个有序链表要求不额外开数组只调整 next 指针。大多数教材讲归并时都用数组举例最后一步要把两个有序数组倒入一个新数组。链表不需要这个操作因为每个节点本身就是独立的只需要把节点的 next 指向正确的位置即可这就是所谓的“原地合并”。合并逻辑不复杂用两个指针分别指向两个链表的头比较当前节点的值把值较小的那个节点接在新链表的尾部然后对应指针后移。直到其中一条链表走完直接把另一条链表的剩余部分接上去。实现时有个小技巧——哑节点dummy node。因为两个链表的头节点中谁的值更小谁才是结果链表的头直接处理的话要单独写一个分支判断头节点。用哑节点的话所有节点都统一从哑节点后面接入最后返回dummy.next即可省去大量特判。ListNode* merge(ListNode* l1, ListNode* l2) { ListNode dummy(0); ListNode* tail dummy; while (l1 ! nullptr l2 ! nullptr) { if (l1-val l2-val) { tail-next l1; l1 l1-next; } else { tail-next l2; l2 l2-next; } tail tail-next; } tail-next (l1 ! nullptr) ? l1 : l2; return dummy.next; }注意比较符号用的是而不是。这一点在 1.2 里提过用能保证值相等时优先取左半段的节点维持稳定性。如果用功能上排序结果不会错但稳定性就没了面试时被问到会很尴尬。合并过程中不需要delete任何节点所有节点都是原有链表上的节点只是改变了 next 指向。这一点和数组归并完全不同数组归并需要额外的 O(n) 空间链表归并的空间开销只有常数级的几个指针。3. 两种实现递归与迭代3.1 自顶向下递归实现递归版最能体现归并排序“分治”的思想先把链表对半切开递归排序左右两段最后合并。代码结构非常清晰和归并排序的数学定义几乎一一对应。class Solution { public: ListNode* sortList(ListNode* head) { if (head nullptr || head-next nullptr) { return head; } ListNode* slow head; ListNode* fast head-next; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; } ListNode* rightHead slow-next; slow-next nullptr; ListNode* left sortList(head); ListNode* right sortList(rightHead); return merge(left, right); } };递归的执行过程可以这样理解sortList 先把整条链切成两段然后分别对两段调用自身。每次调用都会把规模减半直到链表只剩一个节点或空链表——这是递归的终止条件一个节点天然有序直接返回。以链表 4 - 2 - 1 - 3 为例跑一遍递归过程第一次调用快慢指针找到中点切成 4 - 2 和 1 - 3 两段。左段递归 sortList(4 - 2)右段递归 sortList(1 - 3)。sortList(4 - 2) 内部切成 4 和 2两个单节点直接返回。合并后得到 2 - 4。sortList(1 - 3) 同理得到 1 - 3。最后把 2 - 4 和 1 - 3 合并得到 1 - 2 - 3 - 4。这个版本写起来非常舒服几乎不会出指针错误因为它把“切”和“合”的逻辑完全分隔开了。缺点就是递归深度为 O(log n)虽然对链表长度十万、百万级完全没问题但较真的面试官会追问“空间复杂度能不能压到 O(1)”这时候就得拿迭代版了。3.2 自底向上迭代实现迭代版走的是另一个方向。它不是从上往下大块切分而是从 1 个节点开始先把相邻的 1 节点块两两合并成有序的 2 节点块再把相邻的 2 节点块合并成 4 节点块以此类推直到整个链表有序。这个过程没有递归空间复杂度能做到严格的 O(1)。实现迭代版的关键是设计一个cut函数从给定头节点开始切下 n 个节点返回剩余部分的头节点并把切下的部分末尾的 next 置空。ListNode* cut(ListNode* head, int n) { if (head nullptr) { return nullptr; } ListNode* cur head; while (--n cur ! nullptr) { cur cur-next; } if (cur nullptr) { return nullptr; } ListNode* next cur-next; cur-next nullptr; return next; }cut 是迭代版的核心很多 bug 都出在这里。先说--n和n--的区别如果传入 n1表示要切下 1 个节点cur 应该停在头节点位置用--n先自减成 0循环一次都不执行cur 直接指向头节点正确。如果写成n--循环条件先判 n1 为真执行一次 cur cur-next结果把头节点和第二个节点一起切下来了直接出 bug。完整迭代版代码class Solution { public: ListNode* sortList(ListNode* head) { if (head nullptr || head-next nullptr) { return head; } int length 0; ListNode* cur head; while (cur ! nullptr) { length; cur cur-next; } ListNode dummy(0); dummy.next head; for (int step 1; step length; step 1) { ListNode* prev dummy; cur dummy.next; while (cur ! nullptr) { ListNode* left cur; ListNode* right cut(left, step); cur cut(right, step); prev-next merge(left, right); while (prev-next ! nullptr) { prev prev-next; } } } return dummy.next; } };外层 for 循环的 step 从 1 开始每次翻倍代表当前待合并块的大小。内层 while 循环不断从链表中切出左右两块合并后挂到 prev 后面。内层循环里最容易出错的是prev-next merge(left, right)之后的指针移动。合并后的链表长度可能是 step 的两倍也可能是 step右半块不足 step 时不能用固定的步长跳跃所以只能用 while 循环一路走到合并结果的尾部。我第一次写的时候图省事直接把prev prev-next写了一遍结果下一轮循环合并结果没接对链表乱得一塌糊涂。3.3 两种方案怎么选方案时间复杂度空间复杂度代码复杂度适用场景递归自顶向下O(n log n)O(log n)递归栈低思路直观面试中快速写出正确解迭代自底向上O(n log n)O(1)高需要 cut 函数题目明确要求 O(1) 空间我个人的建议是面试时先写递归版把思路讲清楚代码也稳如果面试官追问空间复杂度再切换到迭代版。现实中大部分场景只要能把 O(n log n) 时间复杂度的正确代码写出来就已经能过面试了。但如果笔试平台里明确写了“空间复杂度 O(1)”那就直接上迭代版不用犹豫。4. 边界条件与调试实录4.1 快慢指针的初始化陷阱快慢指针找中点是这道题里最容易翻车的环节翻车点主要集中在 fast 的初始化和循环条件上。如果 fast 从 head 开始那么长度为 2 的链表节点 A - B在循环一次后slow 会走到 Bfast 会走到 null。此时 rightHead slow-next nullptr右半段为空左半段是完整的两个节点相当于没切分成功。虽然最终递归结果也能对但把长度为 2 的链表切出一个空链表明显不合理还多了一次无意义的递归调用。如果 fast 从 head-next 开始长度为 2 时循环直接不执行slow 停在 ArightHead B完美切成两个单节点。循环条件while (fast ! nullptr fast-next ! nullptr)的顺序也不能乱。C 里是短路求值先判断 fast 不为空才能继续判断 fast-next。反过来写虽然编译不报错但链表走到尾部时 fast 已经为空再去取 fast-next 就是访问空指针直接段错误。这两个细节在本地调试时往往不容易暴露因为你们测试的链表通常长度凑巧避开了边界。真正出问题的场景是链表长度为 1、2、3 这三种特殊情况以及链表本身就是升序或降序排列时快慢指针的路径完全不同。写完后务必要用这几个用例逐个验证。4.2 常见的五个翻车现场我把实际调试中遇到的典型问题整理成一张表如果你代码跑挂了优先对着这张表排查问题现象可能原因解决办法空链表传入时崩溃只判断了head-next没判断head nullptr函数入口先写 if (!head排序结果出现环找完中点后没有断开左右两段在递归或迭代切割后把 slow-next 置空合并后丢节点cut 函数里--n写成了n--检查 cut 的循环条件确认切下的节点数正确迭代版第一轮正确第二轮乱merge 后 prev 没有移动到合并结果尾部用while (prev-next ! nullptr)移动到末尾稳定性被破坏merge 比较符号写成改用保证值相等时优先取左半段还有一个隐蔽问题递归版里如果 fast 从 head 开始且链表只有两个节点得到的 rightHead 为空递归有一个分支是 sortList(nullptr)虽然逻辑上没问题但这个空分支会干扰你调试时对“每层该切几段”的判断。写递归版时我通常直接默认 fast 从 head-next 开始这样每次切出来的左右两段都不会为空除非原链表本身就是空的。本地调试链表题有个很实用的习惯写一个打印链表的辅助函数每执行一次 cut 或 merge 后都打印一遍。比如用4 - 2 - 1 - 3测试cut 之后打印两段各自的 head合并后打印当前结果。这比盯着代码空想要高效得多链表指针的错乱几乎只能靠观察输出定位到具体步骤。5. 复杂度分析与面试延伸5.1 复杂度怎么算归并排序的时间复杂度是 O(n log n)这个结论在数组和链表上是通用的但推导过程值得再讲一遍。每一层归并所有节点都会被遍历一次递归版中找中点是每层 O(n)合并也是每层 O(n)迭代版中每一轮 step 翻倍内层循环会遍历整个链表完成所有小块合并同样每轮 O(n)。总共 log n 层所以总时间复杂度是 O(n log n)。空间复杂度上迭代版只用了几个固定指针不管链表多长额外变量就那几个所以是 O(1)。递归版空间复杂度是 O(log n)因为递归调用栈最深能到 log n 层每层都有几个局部变量。这里要注意网上很多博客说“快排空间 O(log n)”是算上了递归栈但“归并空间 O(1)”是指迭代版。你如果写递归版还在空间复杂度一栏写 O(1)那面试官追问就会露馅。有一个容易混淆的点数组上的归并排序空间复杂度是 O(n)因为合并有序数组必须开临时数组链表上的归并排序迭代版空间是 O(1)因为链表节点本来就不是连续存储的合并只需要改写 next 指针。同一个算法在不同数据结构上的空间开销天差地别这正是这道题最值得品味的地方。5.2 延伸与链表中点、合并 K 个链表的关系BM12 做完之后有几个高频题和它直接相关属于一套“链表归并家族”。最基础的是「合并两个有序链表」这是 merge 函数本体。BM12 的 merge 代码可以直接复用。再往后是「合并 K 个有序链表」朴素做法是逐个合并每轮都调用 merge时间复杂度 O(k²n)更好的是用优先队列维护 K 个链表的当前最小头节点复杂度降到 O(n log k)。这个题在面试里出现频率很高和 BM12 的知识点是贯通的。另一条延伸线是「寻找链表的中间节点」。BM12 的快慢指针找中点部分就是从这道题独立出来的牛客和力扣上都有单独的版本。很多链表题都要先找中点比如回文链表、重排链表、有序链表转 BST所以找中点代码最好练到肌肉记忆的程度。最后提一个热词里的「单链表逆序」。链表排序考的是归并链表的反转题考的是另一个经典操作三指针迭代或递归反转。它可以嵌套在很多题里用比如回文链表判断时要先找中点再反转后半段。如果你正在集中刷链表专题建议把归并、找中点、反转这三个基础操作全部练熟链表类的题目基本就都能拆解成这些基本动作的组合了。至于递归和迭代的取舍我个人的习惯是在能控制递归深度的情况下首选递归写法逻辑清晰不容易错但平台明确要求 O(1) 空间那就老老实实写迭代版再多测几组边界用例。这道题的迭代版调通之后你对链表指针的控制力会上一个明显的台阶。