 空间实现)
1. 题目剖析排序链表到底在考什么LeetCode Hot 100里的第148题“排序链表”表面看起来就是一句话给一个无序链表排个序。但做过的人都知道这道题真正难的不是“排序”本身而是题目附带的两个硬性约束——时间复杂度 O(n log n)空间复杂度 O(1)。这两个条件一出来很多“看起来能用”的思路直接被砍掉了。先说结论这道题的考察核心是归并排序思想在链表结构上的落地尤其是“自底向上的迭代归并”。在面试中这题出现频率极高因为它能一次性考察好几项基本功链表指针操作、双指针技巧、分治思想、递归与迭代的取舍、以及对复杂度分析的敏感度。适合的人群也很明确准备面试的人、刷LeetCode Hot 100的求职者、以及想巩固链表基础操作的开发者。为什么说空间复杂度 O(1) 是个关键分水岭因为大部分人第一反应是“把链表转成数组排序完再转回来”。这个思路时间复杂度没问题但额外空间是 O(n)不符合题目进阶要求。还有些人会想用递归归并排序但递归的调用栈深度是 O(log n)严格来说也不满足 O(1) 空间。唯一能完全达标的就是迭代版的归并排序也就是常说的自底向上bottom-up归并。我在刷题初期第一次碰到这题时也踩过“能用就行”的坑——用递归归并交上去时间跑得也不错但面试官追问一句“空间复杂度是多少”就露怯了。所以这篇文章会把递归版和迭代版都讲透重点放在迭代版上顺便聊聊两者各自的适用场景。2. 方案选型为什么链表排序首选归并而不是快排数组排序的时候快速排序是默认选择平均 O(n log n)、常数小、原地排序。但换到链表这个数据结构上快排的优势几乎全部变成了劣势。第一个问题快排依赖随机访问。Partition 操作需要从左右两端往中间扫描数组可以通过下标 O(1) 定位但链表只能从头开始一个个遍历。每一次 partition 都要重新走一遍链表虽然总复杂度理论上还是 O(n log n)但常数因子大得离谱实际运行效率远不如归并。第二个问题元素交换代价高。数组快排可以直接交换两个元素的值链表交换两个节点要处理一堆前驱后继指针容易出错不说还不稳定。相比之下归并排序的两个核心动作——拆分成两半和合并两个有序序列——恰好都是链表的强项。拆分只需要找到中点合并只需要调整指针指向不需要额外空间迭代版也不需要随机访问。所以链表排序选归并本质上是数据结构的物理特性决定的。再来想一个问题为什么题目把时间复杂度卡在 O(n log n)因为基于比较的排序算法理论下界就是 O(n log n)。你要么做到这个上限要么就得换非比较排序的思路比如基数排序。但基数排序对链表这种线性结构来说遍历次数太多实现也复杂面试中基本不指望。所以说白了这道题就是暗示你用归并排序。至于“把链表转数组再排序”复杂度上其实是达标的——时间 O(n log n)、空间 O(n)。但面试官要考的就是链表操作你绕开链表去用数组等于没答到点子上。我自己在实战中也会先问自己一句这题考的是数据结构本身还是考算法思想148题显然是前者所以必须老老实实用链表结构来完成归并。3. 核心技巧拆解找中点、合并链表、控制迭代轮次3.1 快慢指针找中点链表二分的关键操作归并排序的第一步是分治——把链表切成两半。数组切一半很简单length / 2 就行链表没有 length 属性只能遍历一遍求长度或者用快慢指针在一次遍历中定位中点。快慢指针的思路是快指针每次走两步慢指针每次走一步当快指针到达链表末尾时慢指针正好停在中间位置。这个技巧在很多链表题里都会用到比如判断环形链表、找链表倒数第K个节点。在排序链表这道题里它是分治的基础。这里有一个细节很多人第一次会写错快指针的初始化。通常写法是slow head, fast head-next这样当 fast 到末尾时slow 停在中点的前一个节点或中点节点上。对于偶数长度的链表停在哪个位置决定了左右两半的划分。这个我们后面在代码里细说。3.2 合并两个有序链表归并的核心功力归并排序的第二步是合并——把两个已经有序的子链表合并成一个有序链表。这个操作本身是一道独立的LeetCode题21题“合并两个有序链表”在148题里它是被反复调用的原子操作。合并的要点就一句话比较两个链表头节点的值谁小取谁然后移动对应指针直到一方为空再把剩下的整段接上。听起来简单但写的时候要注意虚拟头节点的使用。不用虚拟头的话你得单独处理“第一个节点谁来当头”的逻辑代码会多出不少分支。用了虚拟头节点整个合并过程就变得统一而简洁。我在实际写的时候习惯把 merge 操作独立成一个函数因为自底向上的归并里每一轮都要对很多对小链表执行合并写成函数复用性更好调试起来也清晰。3.3 递归与迭代空间复杂度的分水岭递归版归并排序很好写sortList(head)里先找中点然后递归排序左右两半最后 merge。代码逻辑直观和数组归并的写法几乎一一对应。但它的问题在于递归深度是 O(log n)每次递归调用在栈上都有开销。虽然 LeetCode 的评测通常不会因此报错面试官如果追问“严格 O(1) 空间能不能做到”你就必须拿出迭代版。迭代版的思路是自底向上先把长度为1的相邻子链表两两合并得到长度为2的有序子链表再把长度为2的相邻子链表两两合并得到长度为4的有序子链表不断翻倍直到整个链表有序。整个过程中除了几个指针变量外没有额外空间开销严格满足 O(1) 空间。迭代版的核心难点有两个一是如何追踪“当前要合并的两段子链表”二是如何在每一轮结束后把上一轮的结果衔接起来。这两个问题我在代码实现部分会结合具体代码讲清楚。4. 完整代码实现递归版与迭代版逐一拆解4.1 递归版思路最直观的入门实现先看递归版它的作用是帮助理解归并思想也是很多人第一次能 AC 的版本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* right slow-next; slow-next nullptr; // 递归排序左右两半 ListNode* left sortList(head); right sortList(right); // 合并两个有序链表 return merge(left, right); } 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 head, fast head-next而不是fast head。为什么因为我们要找的是“中点前一个节点”目的是方便切断链表。如果用fast head当 fast 走到末尾时slow 会停在中点节点上切断时你需要再记录right slow-next并把slow-next nullptr逻辑上也能成立但边界情况处理会更绕。不同的初始化方式决定了 slow 的落点这个细节建议自己在纸上画几个例子验证一下画过之后就不会忘。第二切断链表这步非常关键。slow-next nullptr这行就是分治的“分”动作。如果不切断递归排序左半部分时排序函数会一路遍历到原链表的末尾而不是停在中点整个分治就崩了。很多新手在这题上报错都是漏了这行。第三merge 函数里用了ListNode dummy(0)栈上对象。这里要注意生命周期——dummy 是栈上的取它的地址赋给 tail 没问题因为 merge 函数返回的是dummy.next也就是原链表中的某个真实节点不涉及悬垂指针。4.2 迭代版严格 O(1) 空间的正解递归版能过评测但严格来说不满足 O(1) 空间。下面这个迭代版才是完全符合题目要求的实现也是面试中比较加分的写法class Solution { public: ListNode* sortList(ListNode* head) { if (!head || !head-next) return head; // 先求链表总长度 int length 0; ListNode* cur head; while (cur) { length; cur cur-next; } ListNode dummy(0); dummy.next head; // 外层循环子链表长度从1开始每次翻倍 for (int step 1; step length; step 1) { ListNode* prev dummy; // 上一轮合并后的尾节点 ListNode* cur dummy.next; // 当前待处理链表的头 while (cur) { // 切出第一段长度为 step ListNode* left cur; ListNode* leftEnd cut(left, step); if (!leftEnd) break; // 剩余节点不足一段直接接上 // 从 cut 返回的是第一段的末尾第二段的头是它后面的节点 ListNode* right leftEnd-next; ListNode* rightEnd cut(right, step); // 合并左右两段 ListNode* merged merge(left, right); prev-next merged; // 移动 prev 到合并后链表的末尾 while (prev-next) prev prev-next; // cur 指向下一轮要处理的节点 cur rightEnd ? rightEnd-next : nullptr; } } return dummy.next; } // 从 head 开始截取长度为 n 的节点并返回截取段的最后一个节点 // 同时把该节点后面的链接断开 ListNode* cut(ListNode* head, int n) { if (!head) return nullptr; ListNode* cur head; while (--n cur) { cur cur-next; } if (!cur) return nullptr; ListNode* next cur-next; cur-next nullptr; return next ? cur : nullptr; } };等等这个 cut 函数写得不够清晰我重新整理一版更稳定的实现也是我实际在用的版本class Solution { public: ListNode* sortList(ListNode* head) { if (!head || !head-next) return head; int length 0; ListNode* cur head; while (cur) { 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) { ListNode* left cur; ListNode* leftEnd getEnd(left, step); if (!leftEnd) break; ListNode* right leftEnd-next; ListNode* rightEnd right ? getEnd(right, step) : nullptr; leftEnd-next nullptr; if (rightEnd) rightEnd-next nullptr; prev-next merge(left, right); while (prev-next) prev prev-next; cur rightEnd ? rightEnd-next : nullptr; } } return dummy.next; } // 从 head 走 n 步返回走到的节点走不到就返回 nullptr ListNode* getEnd(ListNode* head, int n) { ListNode* cur head; while (--n cur) { cur cur-next; } return cur; } 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; } };这一版的关键逻辑我需要逐条解释。核心变量是prev和cur。prev始终指向“上一段合并结果接到主链表上的位置”也就是每次合并前主链表中当前尾节点。cur是这一轮中当前要处理的子链表的起始位置。每一轮内循环开始前cur dummy.next从主链表的真正头部开始处理。切分操作我单独抽成了 getEnd。它做的事情很简单从给定节点出发走 n-1 步返回走到的节点。如果链表长度不够 n就返回 nullptr。这个函数的返回值有两种判断用途如果leftEnd是 nullptr说明剩余节点不足一段直接把剩余部分接到 prev 后面结束本轮如果rightEnd是 nullptr说明第二段不足 step 长但仍然可以和第一段合并。切断操作顺序有讲究。leftEnd-next nullptr要先做否则right指针就找不到正确位置了。先记录right leftEnd-next再切断 left 段然后再对 right 段做同样的处理。这个顺序错一步指针就乱了。合并后移动 prev 的方式是迭代版最容易写错的地方。你要把 prev 移动到“合并后链表的最后一个节点”上我的做法是while (prev-next) prev prev-next。有经验的读者会发现这是 O(n) 的看起来会让总复杂度退化。但实际上每一轮中每个节点最多被扫描一次一轮下来总扫描次数是 O(n)外层循环有 O(log n) 轮所以总复杂度依然是 O(n log n)不会退化。cur 的更新也容易错。cur rightEnd ? rightEnd-next : nullptr。如果 rightEnd 存在那它指向第二段的末尾后半段的后续节点从 rightEnd-next 开始如果 rightEnd 为 nullptr说明已经没有后续节点了cur 置空。有个隐藏的坑是当第二段不足 step 长时rightEnd 返回的是第二段的最后一个节点rightEnd-next 自然是 nullptr这样 cur 也会被置空不会漏节点。4.3 递归版和迭代版的对比维度递归版迭代版时间复杂度O(n log n)O(n log n)空间复杂度O(log n)递归栈O(1)代码可读性高思路直观较低指针追踪复杂面试风险可能被追问空间复杂度加分项个人建议先理解思想用来入门最终掌握用来面试如果你面试时间紧张至少要能写出递归版如果时间充裕建议把迭代版写熟练。我自己面试时会先说递归版然后主动补充“我还能用迭代实现把空间降到 O(1)”这往往是加分点。5. 常见问题与排查技巧实录5.1 快慢指针死循环与中点错位递归版里最常见的问题就是快慢指针初始化的选择。网上有两种风格一种fast head一种fast head-next。它们导致 slow 的落点不同前者慢指针落在“中点的第一个节点”后者慢指针落在“中点前一个节点”。如果fast head并且你不做调整偶数长度的链表中 slow 会停在中间靠右的节点上切割时左半部分和右半部分的长度比例不是理想的 n/2 和 n/2虽然归并排序不一定非要等分但会让递归深度不稳定。更隐蔽的问题是在某种写法中 fast 可能走到 nullptr 后再访问fast-next导致空指针访问这是 LeetCode 上报 Runtime Error 的常见原因。我的建议是固定一套写法并理解它slow head, fast head-next循环条件while (fast fast-next)。这套写法的保证是奇数长度链表 slow 停在正中间偶数长度停在中间偏左那个节点且 slow 永远不为空。5.2 忘记切断链表导致分治失效这是递归版第二常见的错误。有些人在找完中点后直接递归调用sortList(head)和sortList(slow-next)忘了写slow-next nullptr。结果左半边递归时链表根本没被截断函数会继续往右半边走永远无法收敛到空链表或单节点链表最终栈溢出。排查方法很简单在 sortList 入口处打印 head 的值看看递归调用时传入的链表长度是否在递减。如果你发现长度没减半九成是切断没做。5.3 迭代版中 merge 后丢失链表尾巴迭代版一个高频 bug 是合并完 left 和 right 后prev-next接上了 merged但 merged 的末尾和后面的节点没有正确衔接。具体表现为输出结果里出现“部分有序、部分无序”的奇怪状态。原因是 merge 后的链表尾部还残留着 next 指针。举例如果 left 段有 4 个节点right 段有 3 个节点merge 结束后merged 的尾部节点其实是从 right 段摘过来的一个节点它的 next 原本指向 right 段的下一个节点。如果你没在切分时把rightEnd-next nullptr清掉merge 后的链表尾部就会意外地带着一段原链表顺序自然就乱了。所以迭代版切分时对 left 和 right 都要执行“末端断链”这个动作不能省。5.4 边界条件空链表和单节点链表不管是递归还是迭代第一行都是if (!head || !head-next) return head。这个判断不是模板套话而是必要的边界保护。空链表返回空单节点链表不需要排序直接返回。少了这个判断getEnd 循环里while (--n cur)遇到空指针就会崩。还有一个小细节迭代版外层循环的结束条件是step length不是step length。当 step 翻倍到大于等于 length 时说明所有子链表都已经合并成一个完整链表了再循环没有意义。我在第一次写的时候用了导致多走了一轮虽然没有逻辑错误但浪费了一次 O(n) 扫描。5.5 复杂度分析如何向面试官讲清楚这道题的复杂度分析也是面试考察点。时间上的直观理解是每一轮要对整个链表做一次扫描把相邻的子链表两两合并轮数是 log n 轮因为子链表长度每次翻倍所以总时间 O(n log n)。空间上迭代版只有常数个指针变量满足 O(1)。一个值得准备的问题是“为什么归并排序在链表上比数组上更自然”答案要点有两个合并两个有序链表只需要改指针不需要额外数组拆分链表只需要找中点不需要下标随机访问。数组归并需要 O(n) 辅助空间就是因为合并时要在临时数组里放数据链表不需要。6. 从这道题延伸出去链表排序的变体与实战价值148题刷透之后你会发现自己对链表指针操作的掌控力会提升一个档次。之后的很多题都会用到这里的技巧快慢指针找中点比如回文链表、合并两个有序链表比如合并K个升序链表、断链操作比如重排链表。相当于刷一道题练了三四个核心技能。变形1按值域排序。如果链表节点的值有一个明确范围比如都是 0-9 的整数可以用计数排序的思路遍历一遍统计频次再按频次重建链表。时间复杂度 O(n)但空间 O(k)。这类解法在特定场景下比归并快得多面试中提一嘴可以展示你的知识面。变形2链表稳定排序。归并排序天然是稳定的对于链表这个结构稳定性的价值在于对“携带其他字段的节点”排序时不会打乱相对顺序。有些开发者在处理自定义结构体链表时会特意选归并而不是快排原因就在这里。变形3外部排序。如果你处理的数据量远大于内存比如对磁盘上存储的链表或者更常见的对文件中的大块数据排序归并自底向上的思路就演变成了多路归并外部排序。148题的迭代版实际上是外部排序一个极简的雏形。说一个我个人刷题时的体会。我第一次把迭代版写对花了不少时间主要卡在 cur 的更新上。后来我在纸上画了一个长度为 6 的链表手动模拟 step 1 和 step 2 两轮操作把每个指针的变化都标出来之后整个逻辑就通了。现在每当遇到指针追踪复杂的问题我都会先画图再写代码这是我个人的笨办法但实测下来很稳。最后分享一个小技巧在本地调试时可以写一个printList函数在每一轮迭代结束后打印当前链表状态。这样你能直观看到每一轮子链表如何从长度 1 到长度 2、到长度 4 地有序化。很多时候代码运行结果不对打印一轮状态问题就暴露了。这个习惯在刷所有链表题时都适用比盯着代码硬想要高效得多。 
长河君 · 2026/10/13 2:17:31 · 阅读 1.2k 排序链表 LeetCode 148：自底向上归并排序 O(1) 空间实现
1. 题目剖析排序链表到底在考什么LeetCode Hot 100里的第148题“排序链表”表面看起来就是一句话给一个无序链表排个序。但做过的人都知道这道题真正难的不是“排序”本身而是题目附带的两个硬性约束——时间复杂度 O(n log n)空间复杂度 O(1)。这两个条件一出来很多“看起来能用”的思路直接被砍掉了。先说结论这道题的考察核心是归并排序思想在链表结构上的落地尤其是“自底向上的迭代归并”。在面试中这题出现频率极高因为它能一次性考察好几项基本功链表指针操作、双指针技巧、分治思想、递归与迭代的取舍、以及对复杂度分析的敏感度。适合的人群也很明确准备面试的人、刷LeetCode Hot 100的求职者、以及想巩固链表基础操作的开发者。为什么说空间复杂度 O(1) 是个关键分水岭因为大部分人第一反应是“把链表转成数组排序完再转回来”。这个思路时间复杂度没问题但额外空间是 O(n)不符合题目进阶要求。还有些人会想用递归归并排序但递归的调用栈深度是 O(log n)严格来说也不满足 O(1) 空间。唯一能完全达标的就是迭代版的归并排序也就是常说的自底向上bottom-up归并。我在刷题初期第一次碰到这题时也踩过“能用就行”的坑——用递归归并交上去时间跑得也不错但面试官追问一句“空间复杂度是多少”就露怯了。所以这篇文章会把递归版和迭代版都讲透重点放在迭代版上顺便聊聊两者各自的适用场景。2. 方案选型为什么链表排序首选归并而不是快排数组排序的时候快速排序是默认选择平均 O(n log n)、常数小、原地排序。但换到链表这个数据结构上快排的优势几乎全部变成了劣势。第一个问题快排依赖随机访问。Partition 操作需要从左右两端往中间扫描数组可以通过下标 O(1) 定位但链表只能从头开始一个个遍历。每一次 partition 都要重新走一遍链表虽然总复杂度理论上还是 O(n log n)但常数因子大得离谱实际运行效率远不如归并。第二个问题元素交换代价高。数组快排可以直接交换两个元素的值链表交换两个节点要处理一堆前驱后继指针容易出错不说还不稳定。相比之下归并排序的两个核心动作——拆分成两半和合并两个有序序列——恰好都是链表的强项。拆分只需要找到中点合并只需要调整指针指向不需要额外空间迭代版也不需要随机访问。所以链表排序选归并本质上是数据结构的物理特性决定的。再来想一个问题为什么题目把时间复杂度卡在 O(n log n)因为基于比较的排序算法理论下界就是 O(n log n)。你要么做到这个上限要么就得换非比较排序的思路比如基数排序。但基数排序对链表这种线性结构来说遍历次数太多实现也复杂面试中基本不指望。所以说白了这道题就是暗示你用归并排序。至于“把链表转数组再排序”复杂度上其实是达标的——时间 O(n log n)、空间 O(n)。但面试官要考的就是链表操作你绕开链表去用数组等于没答到点子上。我自己在实战中也会先问自己一句这题考的是数据结构本身还是考算法思想148题显然是前者所以必须老老实实用链表结构来完成归并。3. 核心技巧拆解找中点、合并链表、控制迭代轮次3.1 快慢指针找中点链表二分的关键操作归并排序的第一步是分治——把链表切成两半。数组切一半很简单length / 2 就行链表没有 length 属性只能遍历一遍求长度或者用快慢指针在一次遍历中定位中点。快慢指针的思路是快指针每次走两步慢指针每次走一步当快指针到达链表末尾时慢指针正好停在中间位置。这个技巧在很多链表题里都会用到比如判断环形链表、找链表倒数第K个节点。在排序链表这道题里它是分治的基础。这里有一个细节很多人第一次会写错快指针的初始化。通常写法是slow head, fast head-next这样当 fast 到末尾时slow 停在中点的前一个节点或中点节点上。对于偶数长度的链表停在哪个位置决定了左右两半的划分。这个我们后面在代码里细说。3.2 合并两个有序链表归并的核心功力归并排序的第二步是合并——把两个已经有序的子链表合并成一个有序链表。这个操作本身是一道独立的LeetCode题21题“合并两个有序链表”在148题里它是被反复调用的原子操作。合并的要点就一句话比较两个链表头节点的值谁小取谁然后移动对应指针直到一方为空再把剩下的整段接上。听起来简单但写的时候要注意虚拟头节点的使用。不用虚拟头的话你得单独处理“第一个节点谁来当头”的逻辑代码会多出不少分支。用了虚拟头节点整个合并过程就变得统一而简洁。我在实际写的时候习惯把 merge 操作独立成一个函数因为自底向上的归并里每一轮都要对很多对小链表执行合并写成函数复用性更好调试起来也清晰。3.3 递归与迭代空间复杂度的分水岭递归版归并排序很好写sortList(head)里先找中点然后递归排序左右两半最后 merge。代码逻辑直观和数组归并的写法几乎一一对应。但它的问题在于递归深度是 O(log n)每次递归调用在栈上都有开销。虽然 LeetCode 的评测通常不会因此报错面试官如果追问“严格 O(1) 空间能不能做到”你就必须拿出迭代版。迭代版的思路是自底向上先把长度为1的相邻子链表两两合并得到长度为2的有序子链表再把长度为2的相邻子链表两两合并得到长度为4的有序子链表不断翻倍直到整个链表有序。整个过程中除了几个指针变量外没有额外空间开销严格满足 O(1) 空间。迭代版的核心难点有两个一是如何追踪“当前要合并的两段子链表”二是如何在每一轮结束后把上一轮的结果衔接起来。这两个问题我在代码实现部分会结合具体代码讲清楚。4. 完整代码实现递归版与迭代版逐一拆解4.1 递归版思路最直观的入门实现先看递归版它的作用是帮助理解归并思想也是很多人第一次能 AC 的版本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* right slow-next; slow-next nullptr; // 递归排序左右两半 ListNode* left sortList(head); right sortList(right); // 合并两个有序链表 return merge(left, right); } 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 head, fast head-next而不是fast head。为什么因为我们要找的是“中点前一个节点”目的是方便切断链表。如果用fast head当 fast 走到末尾时slow 会停在中点节点上切断时你需要再记录right slow-next并把slow-next nullptr逻辑上也能成立但边界情况处理会更绕。不同的初始化方式决定了 slow 的落点这个细节建议自己在纸上画几个例子验证一下画过之后就不会忘。第二切断链表这步非常关键。slow-next nullptr这行就是分治的“分”动作。如果不切断递归排序左半部分时排序函数会一路遍历到原链表的末尾而不是停在中点整个分治就崩了。很多新手在这题上报错都是漏了这行。第三merge 函数里用了ListNode dummy(0)栈上对象。这里要注意生命周期——dummy 是栈上的取它的地址赋给 tail 没问题因为 merge 函数返回的是dummy.next也就是原链表中的某个真实节点不涉及悬垂指针。4.2 迭代版严格 O(1) 空间的正解递归版能过评测但严格来说不满足 O(1) 空间。下面这个迭代版才是完全符合题目要求的实现也是面试中比较加分的写法class Solution { public: ListNode* sortList(ListNode* head) { if (!head || !head-next) return head; // 先求链表总长度 int length 0; ListNode* cur head; while (cur) { length; cur cur-next; } ListNode dummy(0); dummy.next head; // 外层循环子链表长度从1开始每次翻倍 for (int step 1; step length; step 1) { ListNode* prev dummy; // 上一轮合并后的尾节点 ListNode* cur dummy.next; // 当前待处理链表的头 while (cur) { // 切出第一段长度为 step ListNode* left cur; ListNode* leftEnd cut(left, step); if (!leftEnd) break; // 剩余节点不足一段直接接上 // 从 cut 返回的是第一段的末尾第二段的头是它后面的节点 ListNode* right leftEnd-next; ListNode* rightEnd cut(right, step); // 合并左右两段 ListNode* merged merge(left, right); prev-next merged; // 移动 prev 到合并后链表的末尾 while (prev-next) prev prev-next; // cur 指向下一轮要处理的节点 cur rightEnd ? rightEnd-next : nullptr; } } return dummy.next; } // 从 head 开始截取长度为 n 的节点并返回截取段的最后一个节点 // 同时把该节点后面的链接断开 ListNode* cut(ListNode* head, int n) { if (!head) return nullptr; ListNode* cur head; while (--n cur) { cur cur-next; } if (!cur) return nullptr; ListNode* next cur-next; cur-next nullptr; return next ? cur : nullptr; } };等等这个 cut 函数写得不够清晰我重新整理一版更稳定的实现也是我实际在用的版本class Solution { public: ListNode* sortList(ListNode* head) { if (!head || !head-next) return head; int length 0; ListNode* cur head; while (cur) { 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) { ListNode* left cur; ListNode* leftEnd getEnd(left, step); if (!leftEnd) break; ListNode* right leftEnd-next; ListNode* rightEnd right ? getEnd(right, step) : nullptr; leftEnd-next nullptr; if (rightEnd) rightEnd-next nullptr; prev-next merge(left, right); while (prev-next) prev prev-next; cur rightEnd ? rightEnd-next : nullptr; } } return dummy.next; } // 从 head 走 n 步返回走到的节点走不到就返回 nullptr ListNode* getEnd(ListNode* head, int n) { ListNode* cur head; while (--n cur) { cur cur-next; } return cur; } 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; } };这一版的关键逻辑我需要逐条解释。核心变量是prev和cur。prev始终指向“上一段合并结果接到主链表上的位置”也就是每次合并前主链表中当前尾节点。cur是这一轮中当前要处理的子链表的起始位置。每一轮内循环开始前cur dummy.next从主链表的真正头部开始处理。切分操作我单独抽成了 getEnd。它做的事情很简单从给定节点出发走 n-1 步返回走到的节点。如果链表长度不够 n就返回 nullptr。这个函数的返回值有两种判断用途如果leftEnd是 nullptr说明剩余节点不足一段直接把剩余部分接到 prev 后面结束本轮如果rightEnd是 nullptr说明第二段不足 step 长但仍然可以和第一段合并。切断操作顺序有讲究。leftEnd-next nullptr要先做否则right指针就找不到正确位置了。先记录right leftEnd-next再切断 left 段然后再对 right 段做同样的处理。这个顺序错一步指针就乱了。合并后移动 prev 的方式是迭代版最容易写错的地方。你要把 prev 移动到“合并后链表的最后一个节点”上我的做法是while (prev-next) prev prev-next。有经验的读者会发现这是 O(n) 的看起来会让总复杂度退化。但实际上每一轮中每个节点最多被扫描一次一轮下来总扫描次数是 O(n)外层循环有 O(log n) 轮所以总复杂度依然是 O(n log n)不会退化。cur 的更新也容易错。cur rightEnd ? rightEnd-next : nullptr。如果 rightEnd 存在那它指向第二段的末尾后半段的后续节点从 rightEnd-next 开始如果 rightEnd 为 nullptr说明已经没有后续节点了cur 置空。有个隐藏的坑是当第二段不足 step 长时rightEnd 返回的是第二段的最后一个节点rightEnd-next 自然是 nullptr这样 cur 也会被置空不会漏节点。4.3 递归版和迭代版的对比维度递归版迭代版时间复杂度O(n log n)O(n log n)空间复杂度O(log n)递归栈O(1)代码可读性高思路直观较低指针追踪复杂面试风险可能被追问空间复杂度加分项个人建议先理解思想用来入门最终掌握用来面试如果你面试时间紧张至少要能写出递归版如果时间充裕建议把迭代版写熟练。我自己面试时会先说递归版然后主动补充“我还能用迭代实现把空间降到 O(1)”这往往是加分点。5. 常见问题与排查技巧实录5.1 快慢指针死循环与中点错位递归版里最常见的问题就是快慢指针初始化的选择。网上有两种风格一种fast head一种fast head-next。它们导致 slow 的落点不同前者慢指针落在“中点的第一个节点”后者慢指针落在“中点前一个节点”。如果fast head并且你不做调整偶数长度的链表中 slow 会停在中间靠右的节点上切割时左半部分和右半部分的长度比例不是理想的 n/2 和 n/2虽然归并排序不一定非要等分但会让递归深度不稳定。更隐蔽的问题是在某种写法中 fast 可能走到 nullptr 后再访问fast-next导致空指针访问这是 LeetCode 上报 Runtime Error 的常见原因。我的建议是固定一套写法并理解它slow head, fast head-next循环条件while (fast fast-next)。这套写法的保证是奇数长度链表 slow 停在正中间偶数长度停在中间偏左那个节点且 slow 永远不为空。5.2 忘记切断链表导致分治失效这是递归版第二常见的错误。有些人在找完中点后直接递归调用sortList(head)和sortList(slow-next)忘了写slow-next nullptr。结果左半边递归时链表根本没被截断函数会继续往右半边走永远无法收敛到空链表或单节点链表最终栈溢出。排查方法很简单在 sortList 入口处打印 head 的值看看递归调用时传入的链表长度是否在递减。如果你发现长度没减半九成是切断没做。5.3 迭代版中 merge 后丢失链表尾巴迭代版一个高频 bug 是合并完 left 和 right 后prev-next接上了 merged但 merged 的末尾和后面的节点没有正确衔接。具体表现为输出结果里出现“部分有序、部分无序”的奇怪状态。原因是 merge 后的链表尾部还残留着 next 指针。举例如果 left 段有 4 个节点right 段有 3 个节点merge 结束后merged 的尾部节点其实是从 right 段摘过来的一个节点它的 next 原本指向 right 段的下一个节点。如果你没在切分时把rightEnd-next nullptr清掉merge 后的链表尾部就会意外地带着一段原链表顺序自然就乱了。所以迭代版切分时对 left 和 right 都要执行“末端断链”这个动作不能省。5.4 边界条件空链表和单节点链表不管是递归还是迭代第一行都是if (!head || !head-next) return head。这个判断不是模板套话而是必要的边界保护。空链表返回空单节点链表不需要排序直接返回。少了这个判断getEnd 循环里while (--n cur)遇到空指针就会崩。还有一个小细节迭代版外层循环的结束条件是step length不是step length。当 step 翻倍到大于等于 length 时说明所有子链表都已经合并成一个完整链表了再循环没有意义。我在第一次写的时候用了导致多走了一轮虽然没有逻辑错误但浪费了一次 O(n) 扫描。5.5 复杂度分析如何向面试官讲清楚这道题的复杂度分析也是面试考察点。时间上的直观理解是每一轮要对整个链表做一次扫描把相邻的子链表两两合并轮数是 log n 轮因为子链表长度每次翻倍所以总时间 O(n log n)。空间上迭代版只有常数个指针变量满足 O(1)。一个值得准备的问题是“为什么归并排序在链表上比数组上更自然”答案要点有两个合并两个有序链表只需要改指针不需要额外数组拆分链表只需要找中点不需要下标随机访问。数组归并需要 O(n) 辅助空间就是因为合并时要在临时数组里放数据链表不需要。6. 从这道题延伸出去链表排序的变体与实战价值148题刷透之后你会发现自己对链表指针操作的掌控力会提升一个档次。之后的很多题都会用到这里的技巧快慢指针找中点比如回文链表、合并两个有序链表比如合并K个升序链表、断链操作比如重排链表。相当于刷一道题练了三四个核心技能。变形1按值域排序。如果链表节点的值有一个明确范围比如都是 0-9 的整数可以用计数排序的思路遍历一遍统计频次再按频次重建链表。时间复杂度 O(n)但空间 O(k)。这类解法在特定场景下比归并快得多面试中提一嘴可以展示你的知识面。变形2链表稳定排序。归并排序天然是稳定的对于链表这个结构稳定性的价值在于对“携带其他字段的节点”排序时不会打乱相对顺序。有些开发者在处理自定义结构体链表时会特意选归并而不是快排原因就在这里。变形3外部排序。如果你处理的数据量远大于内存比如对磁盘上存储的链表或者更常见的对文件中的大块数据排序归并自底向上的思路就演变成了多路归并外部排序。148题的迭代版实际上是外部排序一个极简的雏形。说一个我个人刷题时的体会。我第一次把迭代版写对花了不少时间主要卡在 cur 的更新上。后来我在纸上画了一个长度为 6 的链表手动模拟 step 1 和 step 2 两轮操作把每个指针的变化都标出来之后整个逻辑就通了。现在每当遇到指针追踪复杂的问题我都会先画图再写代码这是我个人的笨办法但实测下来很稳。最后分享一个小技巧在本地调试时可以写一个printList函数在每一轮迭代结束后打印当前链表状态。这样你能直观看到每一轮子链表如何从长度 1 到长度 2、到长度 4 地有序化。很多时候代码运行结果不对打印一轮状态问题就暴露了。这个习惯在刷所有链表题时都适用比盯着代码硬想要高效得多。