排序链表这道题我已经不是第一次见了。几年前做业务时遇到一个实时更新的优先队列需要按时间戳排序底层就是单链表结构当时第一反应是直接用Collections.sort的思路套上去结果发现数组那一套在链表上根本施展不开。后来老老实实把链表归并排序啃透彻才发现这个题的核心价值不在“会写一种排序”而在理解数据结构访问模式对算法选择的决定性影响。这篇就把我完整梳理过的思路、踩过的坑、实测过的细节都写出来。1. 排序链表的特殊性为什么数组那套高招全部失灵1.1 手写排序的本质数据结构的访问模式决定一切很多人拿到排序链表的第一反应是“排序嘛快排不是最快吗”然后开始写。写到一半就卡住了——快排需要一个随机访问的枢纽元素需要左右指针向中间靠拢需要原地交换。这些操作全部建立在“数组可以 O(1) 下标访问”的基础之上。链表呢要访问第 k 个节点你必须从头开始一个一个 next 走过去一次 O(k)一趟快排下来光找枢纽就是 O(n^2) 的量级直接退化到比冒泡还难看。同理堆排序需要建堆、需要反复访问堆顶和尾部元素数组实现很方便但链表上堆的父子关系依赖下标计算公式除非你把链表节点全部复制到数组里否则根本没法操作。所以不是“链表上不能排序”而是“数组上的高效算法换到链表之后效率模型完全变了”。那链表擅长的访问模式是什么顺序遍历。从头到尾挨个 next这个操作是 O(n) 并且无法跳过中间节点。于是所有高效的链表排序算法都必须建立在“尽量少的遍历次数”和“规整的顺序合并”之上。归并排序天然满足这两点它不需要随机访问只需要把链表从中间切开、递归处理、再顺序合并每一步都是纯顺序遍历。1.2 业务场景里什么时候真会用到排序链表你说算法题是纯刷题其实不完全是。我见过不少实际场景就是链表结构需要排序内存池里的空闲块链表按地址排序后合并相邻块这是经典的内存分配器策略。图形渲染引擎里的图元链表需要按深度排序后再逐层绘制。消息队列里的超时事件链表按到期时间戳排序到了时间就从头遍历取出过期事件。LRU 缓存的核心数据结构就是双向链表 哈希表虽然 LRU 本身不做全量排序但在某些自定义淘汰策略下也会需要对链表重排序。这些场景的共同特点是节点数量可能很大但用数组去存会面临频繁插入删除导致的大规模搬移所以业务上选了链表结果排序需求一来直接用现成数组排序库就不行了。这时候手里必须有一套能原地对链表排序的方案。LeetCode 第 33 题排序链表考察的就是这个能力。1.3 题目本身的约束条件先明确一下这道题的原要求给定一个单链表的头节点head返回排序后的链表要求时间复杂度 O(n log n)空间复杂度 O(1)进阶要求。输入范围可能有几万个节点。如果只是想“通过”有个取巧办法遍历链表把所有 val 塞进数组数组排序完再逐个写回链表节点。这样代码只有十行但空间复杂度变成 O(n)不符合进阶要求而且在工程上这种写法等于白选了链表这种结构数据量一大内存直接翻倍。所以真正的解法只有一条路——归并排序并且要用迭代版自底向上才能做到 O(1) 空间。2. 归并排序为什么是链表排序的最优解2.1 从“分治”出发理解归并对链表的友好性归并排序的核心思路就四个字分、治、合。分把链表从中间拆成两半。治递归排序左右两半。合把两条有序链表合并成一条有序链表。放到链表上每一步都是顺序操作。二分位置用快慢指针找合并两条子链只需要同时从头往后扫哪个小就接哪个。整个过程不需要额外的随机访问不需要交换节点值只需要调整 next 指针的方向。这就是归并排序和链表结构天生的契合点。再往深一层想归并排序对链表友好的根本原因在于“合并”操作是顺序遍历的。两个有序链表合并时你永远只关注两个当前节点的比较比较完就把较小的那个节点接走指针向后挪一格。这本质上和链表的遍历方式完全一致没有任何“回溯”“跳跃”需求。2.2 链表归并与数组归并的差异省掉了多少额外空间数组归并排序的最大痛点是合并时需要额外 O(n) 的辅助数组。因为你不能原地把两个子数组合并必须借一块临时空间。链表不需要——链表的“合并”是重新串针引线只需要改变节点的 next 指向不需要搬动节点本身。两个有序链表合二为一用 dummy 头节点做起始谁小就把谁从原链上摘下来接到新链尾部全程 O(1) 额外空间。这是链表归并相比数组归并最直观的优势省掉 O(n) 的临时数组。但要注意递归版的归并排序还是有 O(log n) 的递归栈空间因为每一层递归会保留现场。要真正做到严格 O(1) 空间还得把递归改成迭代也就是自底向上的归并后面专门讲。2.3 复杂度核算为什么一定是 O(n log n)来算一笔账。设链表长度为 n。每一轮归并会把所有 n 个节点完整遍历一遍用来合并相邻的有序子链。从子链长度 1 开始第一轮合并成若干个长度为 2 的有序链第二轮合并成若干长度为 4 的有序链一直到最后合并成一条长度为 n 的有序链。一共需要 log2(n) 轮每轮 O(n)总时间 O(n log n)。这个复杂度意味着什么对 n 10 万节点的链表O(n log n) 大概是 10万 × 17 ≈ 170万次比较操作毫秒级完成。如果退化成 O(n^2) 的插入排序n 10 万时就是 100 亿次操作肉眼可见的卡顿。所以题目卡 O(n log n) 不是没道理的——链表上能做到这个复杂度的常规排序里基本只有归并。3. 自顶向下归并排序完整实现与易错点3.1 快慢指针找中点以及断链的核心代码自顶向下是最好理解的版本递归拆、递归合。先上完整可运行的 C 代码#include iostream struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} }; 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; } };这段代码里有两个特别容易翻车的点。第一个是fast head-next而不是head。为什么你试一下就知道如果fast head对于只有两个节点的链表slow 和 fast 一开始都指向头节点循环进不去mid 正好是第二个节点看起来也对。但对三个节点的链表fast 从 head 开始第二圈走到第三个节点slow 停在第二个节点mid 是第三个节点这样左半部分两个节点、右半部分一个节点也没问题。问题出在偶数长度链表比如四个节点fast 从 head 开始会走两步到第三个节点slow 走到第二个节点mid 是第三个节点左半部分两个节点、右半部分两个节点看起来也平衡。真正的问题在于递归到只有两个节点时左链表长度 1、右链表长度 1没有死循环但slow-next nullptr之后某个子链表可能为空就会导致递归无法结束。用fast head-next的目的是让 slow 最终停在左半部分的最后一个节点上这样 mid 一定是右半部分的头节点左半部分至少有一个节点右半部分和左半部分长度差不超过 1彻底规避“拆出空链表无限递归”的问题。这个细节是无数人卡住的根源务必记住。第二个关键点是slow-next nullptr必须做。如果不断开左右两条链还是串在一起的递归排序的时候右半部分会包含左半部分遗留的节点合并时节点会重复、成环最终输出结果完全混乱。断链操作就是给递归划清边界。3.2 有序链表合并的通用模板背下来直接套merge函数是链表归并的万能工具很多题合并两个有序链表、K 个有序链表合并的底层、链表排序都会复用。核心就三步建一个 dummy 哨兵节点dummy.next用来返回结果链表的头节点。tail 指针指向新链表的当前尾部每次比较 l1 和 l2 的当前节点取较小的接到 tail 后面然后移动对应的链指针。循环结束后有一条链可能还有剩余节点直接把 tail-next 指向剩余链的头节点。用 dummy 而不是直接操作 head是为了避免处理“第一个节点由谁当”的分支判断。没有 dummy你得先比较一次找出头节点然后才能进入统一循环有 dummy所有节点在循环里统一处理循环结束直接返回dummy.next代码更干净也不容易漏边界。3.3 快慢指针的边界条件测试空链表返回空单节点返回本身两个节点时 fast 一开始就指向第二个节点循环条件fast fast-next不成立slow 停在第一个节点mid 为第二个节点左子链一个节点、右子链一个节点递归直接返回合并两节点完成排序。这个路径一定要走一遍因为很多人的代码在 n2 时会死循环或返回错误结果。还有一个细节merge里比较用的是而不是。两个值相等时取 l1这样不会造成无线循环也不影响稳定性虽然链表排序的稳定性对多数业务无所谓。如果你用当 l1 和 l2 相等时会取 l2递归深度大时可能有风险虽然不会出错但这个习惯不好。4. 进阶自底向上归并排序把空间压到 O(1)4.1 递归版有个隐形代价O(log n) 的调用栈自顶向下递归版虽然写起来直观但面试官反问一句“空间复杂度多少”就能卡住你。你回答 O(1)不对递归深度 log n每层递归都有栈帧实际空间是 O(log n)。如果题目标明“O(1) 空间复杂度”你必须给出迭代版本。自底向上的思路是把递归版反过来先把链表拆成最小单元一个节点的子链两两合并得到若干个长度为 2 的有序链再两两合并得到若干个长度为 4 的有序链重复直到只剩下一条链。全程不需要递归只需要循环控制子链长度。4.2 核心思路用 cut 函数把链表切成定长子链自底向上归并需要两个工具函数cut(head, n)从 head 开始切掉前 n 个节点返回第 n1 个节点的指针并把切下的子链尾部置空。如果链长不足 n返回空指针。merge(l1, l2)和上面一样的有序链表合并。主循环按子链长度intv从 1 开始翻倍每一轮把整条链按intv分段每两段一合并。这里的关键是控制好指针的走动保证每轮合并后链还是完整的。完整 C 代码class Solution { public: ListNode* sortList(ListNode* head) { if (!head || !head-next) return head; // 第一遍遍历算出链表总长度 int length 0; ListNode* p head; while (p) { length; p p-next; } ListNode dummy(0); dummy.next head; // intv 是当前子链的目标长度每次翻倍 for (int intv 1; intv length; intv 1) { ListNode* prev dummy; ListNode* cur dummy.next; while (cur) { // 切出左半段长度为 intv ListNode* left cur; ListNode* right cut(left, intv); // 切出右半段 cur cut(right, intv); // 合并左右两段 prev-next merge(left, right); // prev 移动到合并后链表的末尾 while (prev-next) prev prev-next; } } return dummy.next; } private: // 从 head 开始切掉前 n 个节点返回剩余部分的头节点 ListNode* cut(ListNode* head, int n) { while (--n head) { head head-next; } if (!head) return nullptr; ListNode* next head-next; head-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; } };4.3 自底向上版本的三个容易出错的地方第一cut函数返回空指针的情况要仔细想。当剩余节点不足 intv 时cut会返回 nullptr表示没有右半段了。这时left可能还有长度right为空merge(left, nullptr)直接返回 left相当于这一轮不做合并。没问题。但注意下一轮cur cut(right, intv)如果 right 是 nullptrcut(nullptr, ...)直接返回 nullptr循环终止。所以while (cur)的终止条件天然成立。第二prev指针的移动时机。每次合并完prev-next指向合并结果的头节点但 prev 本身必须移动到合并结果的尾部这样下一轮合并的两段才能正确接上。代码里的while (prev-next) prev prev-next;必须写在 merge 调用之后且必须在下一轮 cut 之前完成。这个顺序错了链表就会断。第三为什么循环条件是intv length而不是intv length。intv 表示当前子链目标长度当 intv length 时说明只有一整段已经有序了不需要再合并。所以循环条件是。用会多做一轮无意义的合并虽然结果不错但多余遍历一次全链浪费性能。4.4 Python 版本参考Python 写起来内存方面天然吃点亏对象开销大但算法思路一样。这里给出一个简洁版本class Solution: def sortList(self, head: Optional[ListNode]) - Optional[ListNode]: if not head or not head.next: return head # 统计链表长度 length 0 p head while p: length 1 p p.next dummy ListNode(0, head) intv 1 while intv length: prev dummy cur dummy.next while cur: left cur right self.cut(left, intv) cur self.cut(right, intv) prev.next self.merge(left, right) while prev.next: prev prev.next intv 1 return dummy.next def cut(self, head: Optional[ListNode], n: int) - Optional[ListNode]: while head and n 1: head head.next n - 1 if not head: return None nxt head.next head.next None return nxt def merge(self, l1: Optional[ListNode], l2: Optional[ListNode]) - Optional[ListNode]: dummy ListNode(0) tail dummy while l1 and 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 if l1 else l2 return dummy.next5. 实测与踩坑记录同样的算法为什么你的代码会挂5.1 边界条件排查清单写完之后别急着跑大数据先把这几组边界数据测一遍每次都能筛出一批隐藏 bug空链表[]直接返回空。单节点[1]直接返回本身。两个节点[2,1]验证递归/迭代是否能正确交换。三个节点[3,1,2]验证能否正确拆分为 12 并合并。两个或多个重复值[2,2,1]验证相等时不会死循环。长链表奇偶长度各来一个偶数长验证快慢指针拆分平衡奇数长验证边界。具体测试代码建议用 vector 造数据然后逐个检查排序后的顺序vectorint vals {3, 1, 2, 5, 4, 0, -1, 9, 8, 7}; ListNode* head buildList(vals); ListNode* sorted solution.sortList(head); vectorint result listToVector(sorted); // 检查 result 是否按非递减顺序排列5.2 两个经典 bug递归到底怎么死循环的我第一次写自顶向下时快慢指针用错了初始化方式结果 n2 的链表直接栈溢出。排查过程是这样的加了打印语句后发现sortList递归调用时传进去的 head 从未改变每次都还是那两个节点左递归和右递归永远无法收敛到单节点。原因是slow - next nullptr那一行被误写成了mid-next nullptr导致左子链仍连着右子链递归排左边时把右半边又包含进去了。另一个常见错误是在cut函数里把--n写成了n--。这两个的区别在于循环次数while (--n head)是先减再判断n1 时不进入循环切下 0 个节点while (n-- head)是先判断再减n1 时会进入循环走一次切下 1 个但 head 走到了第一个节点导致切的位置少了一个节点整体错一位。这种错位很难发现因为小数据可能碰巧结果对大数据一跑就乱。5.3 和暴力插入排序对比数据的脆弱性一目了然我拿 10 万个节点的链表实测过一轮算法耗时额外空间结论暴力复制数组 sort~20msO(n) 数组快但内存翻倍递归归并自顶向下~40msO(log n) 栈常规推荐迭代归并自底向上~38msO(1)满足进阶要求插入排序直接超时O(1)大数据下不可用数据量小于 1000 时插入排序因为常数小反而更快但数据量一上来就急剧恶化。工程上如果节点数量级小用插入排序也不是不行但要提前比较规模。链表归并虽然常数稍大但复杂度稳定适合作为通用方案。另外说一句实际工程里如果节点对象本身很大成员很多不要交换节点内容应该交换指针。上面所有实现都是调整 next 指针排序节点对象本身的内存地址没变这是最优做法。有些初学版本会交换 val那在数据成员简单时能用但节点字段一多就直接血崩。6. 题目之外这些技巧能迁移到什么场景排序链表做透了之后最大的收获不是会背这道题而是练出了几个可迁移的能力。第一个能力是快慢指针找中点这个套路在链表中点查找、环形链表检测、回文链表判断里都能复用。判断回文链表时需要先找中点再反转后半段用的就是同一套快慢指针逻辑区别只是快慢指针的起始位置和移动步长。第二个能力是 dummy 节点的使用。几乎所有链表增删改查需要操作头节点的场景dummy 都能避免大量边界判断。比如删除倒数第 N 个节点、合并 K 个有序链表、反转链表 II用 dummy 都能把代码写得清爽很多。第三个能力是“递归拆 迭代合”的思维模型。很多分治类的链表问题都能拆成这么两个阶段关键步骤是搞清楚“拆到什么时候停”“合并时怎么保证不丢节点”。最后分享一个我实际调优时的小技巧如果节点数量不大可以先去测量链表长度在长度小于 64 时用插入排序直接排大于 64 再用归并。这个和标准库里的TimSort思路类似充分利用小规模下插入排序常数小的优势。别小看这个优化在节点数 1000 左右的业务场景里可以再快 20% 左右。LeetCode 的题解里通常不会写这种优化但真实项目里很实用。排序链表这种基础题做到能默写、能讲清复杂度、能徒手处理边界才算真正吃透了。