单链表排序最优解：归并排序原理与C++实现

前几天刷牛客链表专题刷到 BM12 单链表的排序时我一开始的想法很直接链表也是线性结构那直接把数组快排模板改改不就行了结果改到一半就发现问题了——快排的 partition 需要从右往左移动指针而链表节点里只有一个 next 指针回头路根本走不了。这篇文章就把我最终采用的归并排序方案、完整的思考过程以及反复踩过的坑都记录下来。单链表排序这道题在牛客 BM 系列里属于链表专题的中等偏上题目LeetCode 对应的是 148. Sort List。它的价值不只是让你把某个排序算法背出来而是逼你重新审视“数据结构会如何限制算法实现”这也是面试中非常爱问的一类问题。下面从我的翻车经历讲起。1. 为什么数组上玩得熟的那套排序放到链表上全失灵了1.1 一次真实翻车拿着快排思路写链表排序先说我的第一版尝试。当时满脑子都是数组快排的模板选 pivot、左右指针扫描、交换元素。到了链表上第一个问题就让我卡住了双指针从两端往中间逼近这个动作在单链表里根本无法实现因为节点没有前驱指针。我只能退而求其次改成只从头部向右单向扫描的 partition 思路。代码如下// 示意单向扫描版 partition写起来非常别扭 ListNode* partition(ListNode* head, ListNode* tail) { int pivot head-val; ListNode* i head; ListNode* j head-next; while (j ! tail) { if (j-val pivot) { i i-next; swap(i-val, j-val); } j j-next; } swap(i-val, head-val); return i; }这种写法在逻辑上能跑但问题很大第一每次 partition 都要把区间从头到尾扫一遍找边界全靠递归参数代码特别容易错第二链表节点交换值域还算简单如果面试官要求交换节点本身那需要同时维护前驱和后继的四个指针复杂度直接翻倍第三快排在数组上的平均复杂度是 O(n log n)但它的分割点高度依赖随机访问和区间回退放到链表上一旦选到坏的 pivot最坏情况会稳稳退化成 O(n²)。我折腾了一晚上AC 没拿到倒是收获了一堆“野指针”和“无限循环”。这告诉我一个道理不是所有排序算法都适合所有数据结构。1.2 链表结构锁死了哪些算法又成全了哪些算法我把常用的几类排序算法在数组和链表上的适配程度列成了一张表这样看得最清楚排序算法数组上的核心依赖链表上的实现难度结论快速排序随机访问、双向扫描、原地交换单链只能正向移动边界处理复杂pivot 选取受限能做但坑多不推荐堆排序基于下标建堆、频繁随机访问链表按下标访问是 O(n)堆化成本过高基本不可行插入排序从后往前比较、元素后移可从头构建新链但每次查找插入位置都要遍历可行但 O(n²)归并排序顺序划分、合并有序序列只需要顺序访问 修改 next 指针高度契合首选看完这张表就明白了链表没有随机访问能力这个物理限制直接淘汰了一批依赖下标的算法但归并排序本质上只需要“顺序遍历”和“头节点比较”这恰好是链表的强项。数组归并排序通常需要一个 O(n) 的辅助数组来暂存数据而链表版归并只需要调整 next 指针连额外的存储都省了。所以归并排序不是“退而求其次”的选择它本身就是链表排序模型下的最优解。2. 归并排序凭什么成为链表排序的最优选型2.1 归并排序的核心机制一句话就能讲透归并排序说穿了就是三步把序列切成两半把两半分别排序再把两个有序序列合并成一个。递归下去直到每个子序列只剩一个节点——单节点天然有序。合并的过程可以想象成手里有两堆已经排好序的扑克牌每次比较两堆牌的最上面一张哪张小就先拿出来放到结果堆上某一堆空了就把另一堆直接接上去。整个过程只需要朝一个方向取牌不需要回头也不需要跳着访问。这个特性对链表太友好了。链表的 next 指针本来就是单向的归并的“顺序取最小”操作正好顺着 next 方向走天然不冲突。2.2 数据访问模式与链表物理结构的高度契合再往深一层看归并排序和链表之间的契合体现在三个细节上第一归并不需要随机访问。它唯一需要的就是“当前两个链表的头节点”谁小取谁然后头指针往后移动一格。这背后的操作是l1 l1-next是链表的原生操作。第二链表天然支持“切分”。归并分治的第一步是“把序列分成两半”在数组中你要计算下标区间在链表中你只需要用快慢指针找到中间节点然后把中间节点的 next 置空就得到两条独立链表。这种“断开一个指针就能切出一条链”的能力是数组不具备的。第三合并过程不需要新节点。数组归并需要一个长度等于原数组的临时数组来存放结果链表归并只需要把两个链表的节点按大小关系重新串起来节点本身完全不新建不复制空间开销极小。这也是链表归并能做到 O(log n) 甚至 O(1) 辅助空间的根本原因。2.3 时间复杂度和空间复杂度的账咱们一笔一笔算归并排序的复杂度可以用递推式表达T(n) 2T(n/2) O(n)意思是把长度为 n 的链表分成两个长度为 n/2 的子链表分别排序需要 2T(n/2)合并两个有序链表需要 O(n)。根据主定理这个递推式的解是 T(n) O(n log n)。无论输入数据是随机、有序还是完全逆序归并排序都能稳定保持这个复杂度不会像快排那样发生最坏退化。空间方面自顶向下递归版的空间消耗来自递归调用栈每次递归把问题规模减半所以调用深度是 log n辅助空间 O(log n)。自底向上迭代版每层循环只使用常数个指针变量辅助空间可以做到 O(1)。相比之下把链表节点全部塞进 vector 再用sort排序的做法额外空间是 O(n)。面试里聊到这差距一下就拉开了。3. 自顶向下归并先拆到不能再拆再合并出有序链3.1 三个核心动作切割、排序、合并动手写代码之前先想清楚整个递归流程。我当时的拆解是这样的切割用快慢指针找到链表的中点把链表从中间断开得到左右两条子链表。排序递归调用sortList处理左右子链表直到子链表长度变为 0 或 1。合并写一个merge函数把两个已经有序的子链表合并成一条有序链表。其中第 3 步其实可以复用“合并两个有序链表”这道题的函数如果你刷过 BM10应该对merge非常熟悉。链表归并排序本质上就是反复调用这个合并函数。3.2 快慢指针找中点边界条件的细节找链表的中点标准做法是快慢指针慢指针一次走一步快指针一次走两步快指针走到末尾时慢指针恰好在中点附近。ListNode* slow head; ListNode* fast head-next; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; } ListNode* midNext slow-next; slow-next nullptr; // 断开链接这里有一个非常关键的细节fast的初始值到底取head还是head-next。我一开始用的fast head结果链表长度为 4 时slow会停在第三个节点上导致左半部分有 3 个节点、右半部分只有 1 个节点。虽然递归依然能正确排序但子问题分配明显失衡更危险的是在长度为 2 的链表上可能出现左子链表空、右子链表非空的情况处理不当就会无限递归。后来我把fast初始化为head-next这样当链表长度为偶数时slow会停在左半部分的最后一个节点断链后左右两半节点数几乎相等。这种“偏左取中”的策略能最大程度保证递归树平衡。另一个容易漏掉的步骤是slow-next nullptr。这一步是断链如果不做sortList(head)拿到的左半部分实际上还是连着右半部分的递归和合并时就会出现环形链表或者重复节点的问题。我最初好几版的野指针崩溃都出在这。3.3 完整的 C 实现和关键注释把上面几个动作拼在一起就是一份能直接 AC 的代码struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; class Solution { public: ListNode* sortList(ListNode* head) { if (head nullptr || head-next nullptr) { return head; } // 1. 快慢指针找中点 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; // 断开左右两段 // 2. 递归排序左右两段 ListNode* left sortList(head); ListNode* right sortList(rightHead); // 3. 合并两个有序链表 return merge(left, right); } 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; } };merge里的dummy节点是链表题里的经典技巧。因为合并后第一个节点到底来自 l1 还是 l2 不确定用栈上的一个哑节点做头能省去单独的“判断首节点”分支。最后返回dummy.next即是新的头。排序函数里的递归基head nullptr || head-next nullptr覆盖了空链表和单节点链表两种情况这两个条件看起来简单但少写一个就会导致对空指针做head-next的越界访问。3.4 在牛客 BM12 下跑通示例用样例[1, 3, 2, 4, 5]手动推演一遍完整过程链表1 - 3 - 2 - 4 - 5快慢指针找到中点断开成[1, 3]和[2, 4, 5]左半[1, 3]再拆成[1]和[3]单节点直接返回合并得到[1, 3]右半[2, 4, 5]拆成[2]和[4, 5][4, 5]再拆成[4]和[5]合并得到[4, 5]再与[2]合并得到[2, 4, 5]最后合并[1, 3]和[2, 4, 5]逐位比较得到[1, 2, 3, 4, 5]我在牛客平台上提交这个版本示例直接通过运行耗时也正常。对绝大多数参赛和面试场景来说自顶向下归并已经够用了。4. 自底向上归并把递归换成迭代空间压到 O(1)4.1 为什么想摆脱递归自顶向下写法短可读性高但每次递归都要压栈。链表归并的栈深度只有 log n一般不会爆栈可面试官常会追加一句“能不能不用递归实现”。如果题目明确要求 O(1) 额外空间自顶向下就过不了了。除了面试压力还有一个工程上的考量递归本身有函数调用开销节点规模特别大并且链表整体偏有序时迭代版往往跑得更稳。所以我把自底向上的写法也完整梳理了一遍。4.2 从单节点归并开始逐步翻倍迭代思路拆解自底向上的核心思想是先把链表看成 n 个长度为 1 的有序子链表相邻两两合并得到长度为 2 的有序子链表然后相邻两两合并得到长度为 4 的有序子链表以此类推直到步长超过链表长度。伪代码结构如下step 1 while step 链表长度: 从头开始切出两个长度为 step 的子链表 合并它们接到结果链表尾部 继续切下一对直到整条链表处理完 step * 2这里最麻烦的点是“切出定长子链表”。为了复用它我写了一个split辅助函数语义是从 head 开始往后走 step 个节点把第 step 个节点的 next 断开返回下一段的头节点。ListNode* split(ListNode* head, int step) { if (head nullptr) return nullptr; for (int i 1; head ! nullptr i step; i) { head head-next; } if (head nullptr) return nullptr; ListNode* next head-next; head-next nullptr; // 截断 return next; }注意循环里的条件是i step不是i step这样当 step 1 时函数直接截断第一个节点并返回第二个节点不会把第二段也切掉。这个细节我一开始写错过导致左右子链表长度不一致。4.3 迭代归并的完整实现class Solution { public: ListNode* sortList(ListNode* head) { if (head nullptr || head-next nullptr) { return head; } // 计算链表总长度 int length 0; ListNode* p head; while (p ! nullptr) { length; p p-next; } ListNode dummy(0); dummy.next head; // step 从 1 开始每次翻倍 for (int step 1; step length; step 1) { ListNode* cur dummy.next; ListNode* tail dummy; while (cur ! nullptr) { ListNode* left cur; ListNode* right split(left, step); cur split(right, step); tail-next merge(left, right); while (tail-next ! nullptr) { tail tail-next; } } } return 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; } };理解这段代码的关键是内层while循环里三个连续的“切分”动作split(left, step)切出左半部分返回右半部分的头split(right, step)切出右半部分返回下一轮处理段的头然后merge(left, right)把两个子链合并接到tail后面每轮外层循环结束时整个链表已经按当前 step 被重新合并成若干段有序子链表。step 翻倍后继续直到 step 大于等于链表长度。此时dummy.next指向的就是完全有序的链表。空间上算法只使用了dummy、cur、tail、left、right等常数个指针满足 O(1) 辅助空间的要求。时间上依然是 O(n log n)而且完全摆脱了递归。5. 跑通 BM12 之后的复盘那些容易让人卡住的边界和坑5.1 最容易出错的几个点把两种写法都实现、提交、debug 之后我总结出几个非常典型的坑基本每一版错误代码都能归到其中一类。坑一快慢指针初始值导致递归失衡。自顶向下的中点查找fast从head走和从head-next走得到的中点位置不同。我建议统一用fast head-next让慢指针停在“左半最后一个节点”保证拆出的左右两半节点数尽量均匀。坑二忘了断链。slow-next nullptr这一步如果漏掉左右子链表会共享同一段内存。递归排序时右半部分可能被左半部分的递归调用反复处理甚至形成环。表现为程序运行时间异常长、栈溢出、或者输出结果里有重复节点。坑三merge 返回后没有接到正确尾部。自底向上的版本里每合并完一段必须把tail移动到合并结果的最后一个节点。如果tail不更新下一段合并结果会覆盖掉前一段的内容。这里的代码是tail-next merge(left, right); while (tail-next ! nullptr) tail tail-next;坑四合并比较用而不是。当两个链表出现相等值时如果只写相等的节点会从右侧链提前取出虽然仍有序但破坏了归并排序的稳定性。链表节点多的时候相等的节点可能被反复交换位置。用保持左侧优先是稳定性实现的细节。坑五递归基写成head nullptr或head-next nullptr二选一。单链表排序的递归基必须两个都写。只写空节点判断长度为 1 的链表会进入sortList(head-next)的误区只写单节点判断空链表会直接操作空指针。5.2 时间复杂度验证和内存访问模式理论上 O(n log n) 已经是最优的比较排序复杂度但实际跑起来链表归并的常数项比数组归并要大一些。原因是链表的节点在内存中往往不是连续存放的访问l1-next时CPU 无法像数组那样按顺序预取内存块缓存命中率相对低。我拿一个十万节点的随机链表做了个粗略对比自顶向下归并大约需要几十毫秒量级自底向上归并略快一点插入排序则直接跑到了秒级。具体数值受编译优化和数据分布影响很大但结论是明确的在链表上O(n log n) 的归并和 O(n²) 的排序是质变级别的差距别因为“常数大”就选择低阶算法。另外自顶向下和自底向上在时间上差距通常不超过 10%-20%。如果只是应付在线评测二者都不存在问题如果要在面试中证明自己对空间有意识自底向上是更好的谈资。5.3 不同实现的横向对比实现方案时间复杂度空间复杂度可读性推荐场景自顶向下归并O(n log n)O(log n)很高面试首选思路清晰自底向上归并O(n log n)O(1)中等空间受限场景面试加分复制到数组再排序O(n log n)O(n)很高比赛快速过题可投机不推荐面试链表插入排序O(n²)O(1)高链表接近有序时偶尔实用复制到数组再排序这条路做法是把所有节点指针塞进 vector用标准库sort排序再按顺序串起来。代码极短时间复杂度也达标但空间 O(n)。如果面试官要求“不要用额外数组”这种写法基本等于挂在线笔试不限制空间时可以用来抢时间但作为一个长期学习路径我还是建议把归并练起来。6. 从单链表排序延伸出去面试里这道题到底在考什么6.1 为什么大多数人不会想到用归并排序刷题初期几乎所有人背的都是快速排序模板因为数组快排在普通场景里综合表现最好。可一旦数据结构换成链表很多人就“失灵”了不是因为不知道归并而是因为思维被数组模型锁住了。链表题的解题思维和数组题是有本质区别的数组靠下标访问链表靠指针遍历数组可以原地交换链表最小代价的操作是修改 next 指向。这道题的真正考点不是“你会不会写归并代码”而是“你能否根据数据结构特点重新选择算法”。面试官想看的是你做选择时的推理路径而不是直接背答案。6.2 链表的其他排序方案插入排序复杂度高但可做除了归并链表排序还有一条正路是插入排序。思路是用一个新链表的头节点开始遍历原链表每遇到一个节点就从头扫描新链表找到合适的位置插入。ListNode* insertionSortList(ListNode* head) { ListNode dummy(0); ListNode* cur head; while (cur ! nullptr) { ListNode* next cur-next; ListNode* pos dummy; while (pos-next ! nullptr pos-next-val cur-val) { pos pos-next; } cur-next pos-next; pos-next cur; cur next; } return dummy.next; }这个写法对比归并要简单不少但最坏情况 O(n²)。只有在输入链表接近有序、或者链表长度非常短时插入排序才有实际意义。比如长度在 10 以内的链表插入排序反而因为代码简单、常数小表现不差。做题时可以把它作为一个“小规模优化”的兜底策略。6.3 这道题在整个算法体系中的位置单链表归并排序看起来只是一道题实际上它把链表专题里几个最重要的小技巧全部串起来了快慢指针找中点、dummy 哨兵节点、尾插法合并、断链与重组、递归到迭代的转换。一个能独立写出两种归并版本的人大概率也能轻松处理“合并两个有序链表”“合并 K 个有序链表”“链表找环”这些进阶题。我自己的体会是链表归并这类题写一遍感觉不深连续写三遍才真正有手感。第一遍能照猫画虎 AC第二遍能默写出完整代码第三遍能在纸上画出每一步指针的变化。如果面试只有一天准备时间我建议优先把自顶向下版本练到滚瓜烂熟再把自底向上版本的split逻辑吃透这两个版本覆盖的边界情况基本能让链表题的正确率上一个台阶。