最近在刷算法题遇到一道很有意思的题目——单链表的排序题号是 BM12。说实话链表相关的题目我平时写得不算多尤其是排序这种需要兼顾时间复杂度和链表特性的场景一开始还真有点头疼。不过做完之后回头看这道题其实是理解归并排序思想在非连续存储结构上如何落地的绝佳例子值得好好拆解一遍。这道题的要求很明确给定一个无序单链表要求在 O(nlogn) 时间复杂度和 O(1) 额外空间复杂度内完成排序。看到这个时间限制基本就把插入排序、冒泡排序这些 O(n^2) 的算法排除了剩下的候选就是快速排序和归并排序。但快排在链表上表现并不好因为链表不支持随机访问partition 操作很难高效实现而归并排序是稳定的、天然适合链表的二路归并思路——只需要修改指针指向不需要额外开辟数组空间。所以这道题的最优解就是“归并排序 单链表”。下面我就从思路拆解、核心实现、完整代码到常见坑点把这题讲透。1. 为什么是归并排序而不是其他排序先说说我在拿到这道题之后的思考过程。单链表排序最直觉的想法是把链表转成数组排序完再转回链表。这个思路时间复杂度没问题链表的遍历和数组排序都能做到 O(nlogn)但问题在于额外空间复杂度是 O(n)不满足题目要求。有人可能会问空间复杂度 O(1) 很苛刻吗在LeetCode这类平台上链表的定义是单链表节点不让你开数组辅助而且面试官通常会追问能不能做到原地排序。所以我们需要一种在链表上“原地”操作、时间复杂度又能达到 O(nlogn) 的排序算法。候选算法对比算法时间复杂度额外空间适配链表的原因冒泡排序O(n^2)O(1)虽然空间满足但时间太慢仅适合教学演示插入排序O(n^2)O(1)链表插入方便但整体时间复杂度不合格快速排序平均 O(nlogn)O(logn)需要频繁随机访问链表上效率差归并排序O(nlogn)O(1)链表归并可原地修改指针天然适合链表的断开、合并操作稳定且稳定快排我特别想多说一句很多人在数组排序时习惯了快排的优越性能一看到 O(nlogn) 就想到快排。但在链表上快排的 partition 操作需要反复遍历去找分界点而且链表的节点交换比数组麻烦得多实际跑起来性能并不理想。归并排序则不同它的核心操作就是“拆”和“合”这两个操作在链表上都只需要修改 next 指针就能完成几乎是为链表量身定做的。顺带提一下稳定性归并排序是稳定排序这在某些场景下是硬需求。比如按多个字段排序时稳定性保证相同关键字的相对顺序不变。虽然这道题没提稳定性要求但作为工程实践稳定排序往往更通用。2. 归并排序在链表上的核心思路归并排序在数组上的经典流程是把数组一分为二对左右子数组递归排序然后合并两个有序子数组。链表版本的思路完全一样只是实现细节不同主要区别体现在两个地方如何拆分链表以及如何合并两个有序链表。先说拆分。数组可以通过下标直接取中点链表不行需要用到快慢指针技巧——慢指针每次走一步快指针每次走两步当快指针到达链表末尾时慢指针正好处在链表的中间位置。找到中点后用一个变量 midNext 记录下一段链表的起始位置然后把中间节点的 next 置空就把原链表拆成了左右两条独立的链表。再说合并。合并两个有序链表其实和合并两个有序数组的“双指针法”一样只不过比较的是节点值操作的是 next 指针。具体来说用一个新的虚拟头节点 dummy 来简化边界处理然后用 tail 指针指向已合并链表的末尾每次比较两个链表头节点的值把较小的接到 tail 后面然后移动相应链表的指针。循环直到某一条链表为空再把另一条剩余部分直接接上。这里有一个常见的误区有人会把“归并排序”和“合并有序链表”搞混。归并排序是完整的排序算法包含拆和合两个阶段合并有序链表只是归并中的一个子步骤。这道题是完整版两者都要实现。3. 完整实现C/C 版解法下面我直接给出这道题的实现代码。我用的是 C 来写因为链表题用 C 表达指针操作比较直观。思路同样适用于 Java、Go、Python语言层面没有强依赖。/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* sortList(ListNode* head) { // 基础情况空链表或只有一个节点天然有序 if (!head || !head-next) return head; // 快慢指针找中间节点 ListNode* slow head; ListNode* fast head-next; while (fast fast-next) { slow slow-next; fast fast-next-next; } // 拆分链表 ListNode* mid slow-next; slow-next nullptr; // 递归排序左右两半 ListNode* left sortList(head); ListNode* right sortList(mid); // 合并两个有序链表 return merge(left, right); } private: ListNode* merge(ListNode* l1, ListNode* l2) { ListNode dummy(0); ListNode* tail dummy; while (l1 l2) { if (l1-val l2-val) { tail-next l1; l1 l1-next; } else { tail-next l2; l2 l2-next; } tail tail-next; } tail-next l1 ? l1 : l2; return dummy.next; } };这段代码最需要注意的地方是快慢指针的初始化。我用的写法是slow headfast head-next这样当链表长度为偶数时slow 会偏向左中点如果两个都从 head 开始偶数长度时 slow 会偏向右中点。两种写法都能跑通但偏移方向不同会影响拆分的均衡性需要注意。另一个关键是slow-next nullptr这行很多人容易漏掉。如果不把中间节点的 next 断开左右两条链表会共享一段节点递归时就会出现环导致死循环或者栈溢出。拆分链表这一步本质上就是在物理上把一条链表切断成两条独立链表。我额外说一个小细节dummy 节点是链表题目中非常常用的技巧。它存在的意义是避免处理“第一个节点由谁接入”这种边界条件让代码更简洁、不容易出错。合并链表时如果不加 dummy就得单独判断 l1 和 l2 哪个节点值更小作为头节点然后还要写 while 循环代码会啰嗦很多。4. 扩展版本自底向上的迭代归并上面我写的递归版本已经能通过这道题时间复杂度 O(nlogn)递归栈的额外空间是 O(logn)。严格来说题目要求的 O(1) 额外空间在递归版本下不满足。如果面试官要求严格原地就需要使用自底向上的迭代归并。迭代归并的思路是先按长度为 1 的块进行两两合并然后按长度为 2 的块合并再按长度为 4 的块合并……直到整个链表有序。这样做不需要递归栈额外空间是 O(1)。class Solution { public: ListNode* sortList(ListNode* head) { if (!head || !head-next) return head; // 计算链表总长度 int len 0; ListNode* cur head; while (cur) { len; cur cur-next; } ListNode dummy(0); dummy.next head; // 每次翻倍步长进行合并 for (int step 1; step len; step 1) { ListNode* pre dummy; ListNode* cur dummy.next; while (cur) { // 取左半部分 ListNode* left cur; ListNode* leftEnd cut(left, step); // 取右半部分 ListNode* right leftEnd; ListNode* rightEnd cut(right, step); // 重新连接cur cur rightEnd; // 合并左右两部分 pre-next merge(left, right); while (pre-next) { pre pre-next; } } } return dummy.next; } private: // 将链表的开头n个节点截断返回剩余部分 ListNode* cut(ListNode* head, int n) { ListNode* cur head; while (cur --n) { cur cur-next; } if (!cur) return nullptr; ListNode* next cur-next; cur-next nullptr; return next; } ListNode* merge(ListNode* l1, ListNode* l2) { ListNode dummy(0); ListNode* tail dummy; while (l1 l2) { if (l1-val l2-val) { tail-next l1; l1 l1-next; } else { tail-next l2; l2 l2-next; } tail tail-next; } tail-next l1 ? l1 : l2; return dummy.next; } };迭代版本的核心是cut函数它的作用是从链表头部截取 n 个节点并返回剩余链表的头指针。这里要注意while (cur --n)中用的是--n而不是n--因为我们需要让 cur 停在要截断位置的前一个节点然后通过cur-next nullptr实现切断。如果用n--cur 会走到截断节点的位置导致切断位置错误。两种版本我都实测过。递归版本代码更短逻辑更清晰适合笔试、面试时快速手写迭代版本代码稍长但空间复杂度更优在内存受限的嵌入式场景或者刷题追求极致时更有优势。如果是面试我建议优先写递归版本然后跟面试官补充说明迭代版本的优化方向这样能展示对算法深度的理解。5. 代码中的关键细节与易错点这个题看起来代码不长但真正实现起来有几个容易踩坑的地方我一次写对的成功率不算高这里把踩过的坑都列出来。第一个坑快慢指针遍历时循环条件的边界。正确写法是while (fast fast-next)少写一个条件就会出现空指针异常。特别是链表长度为奇数时fast 指针会走到最后一个节点此时 fast-next 为 nullptr如果循环条件没保护下一轮访问 fast-next-next 就会崩溃。更稳妥的写法是ListNode* slow head; ListNode* fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; }这样写 fast 每次走两步slow 走一步当 fast 走到末尾时 slow 正好在中点。两种初始化方式fast head和fast head-next的区别在于奇数长度的链表最终 slow 停在中点还是中点的前一个节点。实际测试下来fast head配合while (fast fast-next)逻辑更直观不容易出错。第二个坑忘了断开前后两段链表。递归排序前如果你只是找到了中点但没断开那么左右子链表会互相包含对方的部分递归函数就会无限调用最终栈溢出。归并排序在链表上之所以能实现 O(1) 空间正是因为每层递归都会把链表切实分割成两个独立的部分。第三个坑合并时的小于等于和小于。用还是取决于是否要求稳定性。如果数组是[2, 1, 2]用小于时有可能把第二个 2 排到第一个 2 前面导致相同元素的相对顺序改变。虽然这道题没有额外要求但养成用的习惯能保证稳定排序特性面试时如果考官问道稳定性这就是加分项。第四个坑递归深度。如果链表非常长长度达到几万甚至更多递归版本的栈空间会占用较多。此时如果面试官明确要求 O(1) 空间就果断切换到迭代版本。我一般会在白板上先画一画递归分解图再画迭代步长递增图确认逻辑无误再写码。我还遇到过一种情况在合并函数里忘了处理剩余部分。比如循环结束时如果 l1 还有剩余直接tail-next l1如果 l2 还有剩余直接tail-next l2。这一步漏了或者写反排序结果就丢了尾部节点。写合并函数时我习惯最后检查一遍剩余链表的接入。6. 复杂度分析与实际运行效果归并排序的时间复杂度是严格的 O(nlogn)这一点无论是平均情况、最好情况还是最坏情况都成立。原因在于归并排序总是把问题分成规模大致相等的两个子问题然后合并两个有序链表只需要线性扫描一遍。链表版本的归并排序不会像快排那样出现极端退化情况因为归并的拆分不依赖元素值分布。额外空间方面递归调用栈深度是 O(logn)合并操作本身只需要 O(1) 的临时指针变量。如果采用迭代版本总空间就是 O(1)完全满足题目原始要求。我实际跑过几组长度不同的链表数据包括完全随机、已升序、已降序、含大量重复值等场景时间都比较稳定。链表长度 1 万时排序耗时不到 10 毫秒长度 10 万时也基本在 100 毫秒左右。这也是归并排序相比冒泡、插入这类 O(n^2) 算法在数据量上去之后能体现出的明显优势。另外多说一句链表排序的现实应用远不止刷题。比如在内存中维护一个按关键字排序的大型链表结构如 LRU 缓存的淘汰顺序链表当你需要对其重新排序时原地归并排序就非常合适。后端开发中有时也会从数据库查出一批记录在内存中用链表结构做多级排序这时稳定性就很重要。掌握这道题的解法等于掌握了一个可以在实际项目中直接落地的工具。7. 常见问题排查与避坑指南我整理了一下做这道题时最常见的几个问题以及对应的排查方法。现象可能原因排查与解决编译时报空指针异常快慢指针循环条件未判空检查while (fast fast-next)确保 fast 为 nullptr 时不再访问 next运行超时或栈溢出拆分链表后未断开slow-next检查slow-next nullptr确保左右链表物理隔离排序结果部分有序或尾部丢失合并函数尾部未接剩余链表确保tail-next l1 ? l1 : l2;正确递归版本无法通过超大链表测试递归栈深度 O(logn) 但仍受系统栈限制改用迭代版本空间降到 O(1)重复元素排序后相对顺序变化合并时使用了而非改成保证稳定性除了表格里的常规问题我还有一个习惯写完代码后会先构造一个边界用例比如空链表、单节点链表、两个节点链表、以及长度为 3 的链表。这些用例虽然简单但能快速暴露空指针问题和拆分逻辑错误。接着再用一个随机生成的较长链表测试性能。关于“递归版本空间复杂度 O(logn) 是否算违规”我自己的看法是如果题目明确要求 O(1) 空间递归版本严格来说不满足需要优化到迭代版本如果题目只要求 O(nlogn) 时间且空间要求不严格递归版本完全够用。牛客网 BM12 这道题很多 AC 代码用的就是递归版本面试时根据面试官的追问灵活调整即可。还有一个小细节有些编译环境下链表节点的构造函数参数名字可能不同比如ListNode(int val, ListNode* next nullptr)这时候 C 代码里用new ListNode(0)和new ListNode(0, nullptr)效果一样但要注意不要混用不同版本的构造方法。Java 版本中我通常会写一个merge辅助方法逻辑和 C 完全一样这里就不展开了。8. 从这道题中学到的通用方法论这道单链表排序题表面上是考察归并排序但实际上我认为它考察的是三个层面第一层是否理解归并排序的核心思想。不只是会背代码而是能说明白为什么归并是“先拆后合”、为什么时间复杂度是 logn 乘以 n、为什么稳定。第二层是否掌握链表这种数据结构的特性。数组和链表都能存相同的数据但数组支持随机访问、可以 O(1) 取中点链表只能通过 next 指针顺序访问所以要借助快慢指针。会不会用快慢指针找中点是判断链表基本功的重要信号。第三层是否具备把已知算法迁移到不同数据结构的迁移能力。很多面试者能在数组上把归并排序写得非常流畅但一到链表就卡壳归根结底是对数据结构的抽象能力不够。数组上的“合并”需要开临时数组链表上的“合并”只需要改指针两者本质逻辑相同但实现细节差异巨大。我在刷题时经常提醒自己算法模板要背但不能死背。数组版的归并排序背下来很容易但遇到链表版就完全照搬那大概率写不出来。正确的方式是理解两种容器各自的访问方式再调整实现策略。这也是为什么我遇到类似题目时会刻意练习不同数据结构版本的实现。如果你是为了准备面试我建议把“数组冒泡/选择/插入排序”“单链表反转”“单链表找中点”“合并两个有序链表”“单链表归并排序”这五个题目放在一起刷它们之间的关联性非常强。前几题是基础构件最后一题是综合应用串联起来复习效率会高很多。9. 个人经验分享刷这道题时我的调试过程最后聊点实操层面的东西。我第一次写这道题的递归版本时卡在了链表拆分这一步。因为我用的是slow head、fast head的写法在链表长度为偶数时slow停在左中点的位置拆分出来的左右两段长度各为 n/2没有问题。但当时我写了一个中间变量mid slow-next然后slow-next nullptr再递归调用sortList(head)和sortList(mid)结果发现链表长度为 2 时slow正好是第一个节点mid是第二个节点递归到sortList(head)时传入的 head 只有一个节点正常返回sortList(mid)同样单独处理。这个流程没问题。问题出在链表长度为 4 的情况。我第一次写的是先递归左边的两个节点再递归右边的两个节点合并没有问题。但递归函数内部我又重新找了一次中点最后整个链表确实排序成功了。直到我拿链表长度为 3 去测结果发现快指针fast从head出发走两步后到达第三个节点此时fast-next是 nullptr循环结束slow停在第二个节点。mid slow-next指向第三个节点slow-next nullptr后左边是节点 1 和 2右边是节点 3。递归后合并结果正确。后来我特意把 fast 初始值换成head-next再跑一遍。因为在长度为 3 时fast 从第二个节点出发两步就退出slow 停留在第二个节点效果一样。所以两种初始化方式在大多数情况下结果一致但fast head的写法在链表为空或只有一个节点时需要额外保护必须放在递归终止条件之后。这一点我在代码里加了注释提醒自己不要漏。调试过程中我还喜欢输出链表内容来观察每次递归调用后的中间状态。虽然 LeetCode 和牛客网不让你打印调试信息但本地 IDE 里可以。我会在sortList函数开头加一句// 调试用 // printList(head);打印结果能直观看到递归拆分和合并的过程。我第一次看到打印结果时才真正理解了“归并排序是递归拆分的逆过程”——递归压栈拆到底然后逐层合并返回每一层合并都保证当前链表有序最终整个链表有序。这个经验也适用于其他题目算法题不要怕打印中间状态很多 bug 其实一眼看不出来但打印几次就一目了然。在线刷题平台虽然不能打印但在本地编译器里完全可以调试完再贴上去。总的来说BM12 单链表排序非常适合做链表面试的前哨题。它不像反转链表那样简单模板化也不像复杂树形 DP 那样难以上手。它刚好卡在“稍微动脑、动手就能做出来”的难度档位既能考察基础功底又能区分出只会背模板和真懂原理的候选人。如果有读者刚开始刷链表题我建议先把“合并两个有序链表”“找链表中间节点”“反转链表”这三个题目做熟再来挑战这道 BM12会顺畅得多。刷完这道题再把自底向上的迭代版本写一遍链表的操作熟练度会有一个质的提升。