企业官网建设流程全解析

排序链表这道题，我相信很多人在刷题平台上都见过它的编号——148。题面一句话就能说清：给你一个单链表，把它排成升序。但这句话背后捆着两个硬条件：时间复杂度要 O(n log n)，额外空间要常数级。这两个条件一出来，这道题就从"排序"变成了"数据结构基本功考察现场"。

我第一次独立写这题时，第一反应是快排，毕竟数组题里快排是王者。结果写完一跑，各种段错误，调试调到头秃。后来才意识到，链表这玩意儿没有随机访问，快排那套"选 pivot、从两头交换"的玩法根本施展不开。这题的真正解法是归并排序，而它恰好把快慢指针、链表切断、有序链表合并这几项基本功全都串起来了。不管你是准备面试，还是平时写代码遇到链式结构需要排序，这题都值得彻底吃透。

1. 拿到题先别急着写代码：三个约束决定算法选型

1.1 题目的隐藏信息

先别急着动手，把题面里没明说的话挖出来。链表排序看起来和数组排序是一回事，实际上差别巨大。

数组支持 O(1) 随机访问，也可以从末尾往前遍历，所以归并排序、快速排序、堆排序都能直接套。但单链表只有 next 指针，你只能从头走到尾，想取任意位置的元素，必须从头走一遍。这意味着所有依赖"下标跳转"的算法在链表上都要重新设计。

更关键的是空间约束。有人会想：那我先把链表遍历一遍放进数组，用 sort 排序，再重新建链表。时间复杂度确实能到 O(n log n)，排序库函数在大多数平台都够快，但额外空间是 O(n)。如果面试官卡常数空间，这个方案当场出局。所以"转数组再排回来"只能作为面试时的过渡思路提一嘴，不能当最终答案。

真正可行的方向就两个：归并排序，或者链表变体快速排序。再仔细一比，归并排序在链表上的优势几乎是碾压级的，下面细说。

1.2 为什么是归并而不是快排

很多人在数组上习惯了快排，到链表上也想用快排。我当初也是这么想的，然后被现实教育了一顿。快排在数组上高效，依赖两件事：随机访问取 pivot，以及从两端向中间扫描做 partition。链表这两个都不满足。

链表快排要取中间节点当 pivot，你得先遍历一次；partition 的时候你又不能从右往左走，只能在单向遍历过程中用"小于 pivot 的节点往前挪"这种笨办法。每次 partition 都是 O(n)，且链表快排对有序输入极度不友好——每次取到头节点当 pivot，最坏情况下退化成 O(n²)。你想想，面试官让你写链表排序，你写了个 O(n²) 的答案，那基本是送命题。

而归并排序就不一样了。它的核心操作只有两个：拆分和合并。拆分靠快慢指针找中点，合并靠"两个有序链表头节点比较"。这两个操作天生就适合链表，因为它只需要改 next 指针，不需要搬动节点数据。链表归并排序时间复杂度稳定在 O(n log n)，和输入是否有序无关，这一点比快排让人放心得多。

1.3 两种归并路线怎么选

确定了归并排序之后，还有两条路线：自顶向下递归，和自底向上迭代。

自顶向下好理解：把链表对半拆开，递归排序两半，然后再合并。写起来思路清晰，面试时讲起来也直观。但递归有递归栈的开销，深度是 O(log n)，严格来说不算常数级空间。很多平台的题解标注"空间 O(1)"，其实指的是迭代版本。

自底向上则完全不同。它不用递归，而是从长度为 1 的有序段开始，两两合并成 2、4、8……逐轮扩大，把整条链表变成一条大的有序段。整个过程只用几个指针变量，空间真正是 O(1)。

我的建议是两条路线都得会。面试时先写自顶向下版，讲清思路；如果面试官追问"能不能把空间压到 O(1)"，再切到自底向上版。两个版本核心都是 merge 函数，代码复用度很高，切换成本很低。

2. 两个基础动作先练熟：找中点和合并有序段

2.1 快慢指针不只是"走两步"

快慢指针是链表题里出现频率最高的技巧之一，找中点只是它最基础的应用。它的原理很直白：两个指针同时从头出发，慢指针每次走一步，快指针每次走两步。当快指针走到链表末尾时，慢指针恰好走了快指针一半的路程，也就是链表的中点。

但这里有个细节很容易翻车：怎么处理偶数长度的链表？比如链表有 4 个节点，快慢指针走完，慢指针落在第 2 个节点还是第 3 个节点？这取决于快指针的起点。我习惯让 fast 从 head->next 出发，循环条件是while (fast && fast->next)，这样慢指针会落在左半段的最后一个节点上，而不是右半段的开头。这个"偏左"的定位是有讲究的，它让左半段永远不会为空，递归时不会出现空指针解引用。

很多人写快慢指针时不注意这个"偏左还是偏右"的问题，结果递归到某一层发现左半段是空的，或者两个子链表长度比例失衡，输出就乱了。这个细节看着小，实际是链表归并最容易埋坑的地方。

2.2 合并函数里的虚拟头节点

合并两个有序链表是这道题的另一半核心。思路是：两个指针分别指向两个链表的头，比较当前节点的值，谁小就把谁接到结果链表后面，然后指针后移，直到其中一个链表为空，再把另一个链表剩余部分整体接上。

工程实现上有一个非常重要的技巧：虚拟头节点（dummy node）。为什么要它？因为合并结果链表的第一个节点是不确定的——有可能是左链表的头，也可能是右链表的头。如果没有 dummy，你就得每次判断"结果链表是不是空的"来决定是直接赋值头节点还是走到尾节点追加。有了 dummy，所有节点都统一走"p->next = 谁"这条路径，最后返回 dummy.next 就行，分支判断少了一半，代码立刻清爽。

这个技巧在单链表很多场景都通用，比如删除倒数第 N 个节点、插入排序、两两交换节点。我用一次记一次教训：头节点可能变化的地方，先建 dummy 准没错。

2.3 动手前先搞清"切断"

归并排序的拆分和数组的"mid = (left + right) / 2"不一样。数组拆分是逻辑上的，左右子数组还在同一块内存里，靠下标区分；链表拆分是物理上的，你必须把中间节点后面的 next 指针置空，让左半段和右半段真正变成两条独立的链表。

这个"切断"动作如果忘了做，麻烦马上就来了。递归调用 sortList(左半段) 时，如果没有切断，左半段其实还连着右半段，整个链表会反复被处理，轻则性能爆炸，重则直接递归死循环。我见过太多人在这道题上栽跟头，就是少了slow->next = nullptr这一行。

切断的位置也有讲究。快慢指针找到中点后，慢指针停在左半段末尾，中点的下一个节点就是右半段开头。你需要先记下ListNode* rightHead = slow->next;，再执行slow->next = nullptr;。顺序反了的话，rightHead 就取不到了，因为 next 已经被置空。

3. 递归版自顶向下：最容易写对的版本

3.1 先上完整代码

先把完整的自顶向下实现贴出来，后面再逐步拆解。

class Solution { public: ListNode* sortList(ListNode* head) { // 递归出口：空链表或只有一个节点，天然有序 if (!head || !head->next) return head; // 快慢指针找中点，slow 最终停在左半段的末尾 ListNode* slow = head; ListNode* fast = head->next; while (fast && fast->next) { 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); } private: ListNode* merge(ListNode* l1, ListNode* l2) { ListNode dummy(0); ListNode* p = &dummy; while (l1 && l2) { if (l1->val <= l2->val) { p->next = l1; l1 = l1->next; } else { p->next = l2; l2 = l2->next; } p = p->next; } p->next = l1 ? l1 : l2; return dummy.next; } };

核心逻辑就三步：找中点、切两半、递归排完再合并。整个函数结构非常对称，理解了一层的逻辑，也就理解了全部层级。

3.2 用 4->2->1->3 走一遍

光看代码不够，拿一个小链表完整走一遍。假设输入是 4 -> 2 -> 1 -> 3。

第一次调用 sortList(head)，链表长度 4，快慢指针走完，slow 停在节点 2 上，rightHead 指向 1，执行slow->next = nullptr后，链表被切成两条：左半段 4 -> 2，右半段 1 -> 3。

然后递归排序左半段 4 -> 2。长度 2，快慢指针走一轮，slow 停在 4，rightHead 指向 2，切断后变成 4 和 2 两条单节点链表。单节点直接返回，merge(4, 2) 得到 2 -> 4。左半段排序完成。

右半段 1 -> 3 同理，排序后得到 1 -> 3。

最后 merge(2->4, 1->3)：比较头节点，1 比 2 小，先接 1；再比较 3 和 2，接 2；再比较 3 和 4，接 3；最后 4 直接接到尾部，得到 1 -> 2 -> 3 -> 4。排序完成。

注意这个过程里，任何一层递归返回的都是"排好序的链表头"，而原链表的物理结构已经被完全改变了。节点没有新增也没有删除，只是 next 指针被重新串了一遍。

3.3 递归版的优缺点

递归版最大的优点是清晰。它把一个大问题分解成两个同样结构的子问题，符合归并排序的数学表达，面试时你讲起来也顺畅——"先拆到最小单元，再逐层合并"。

但它有两个不能忽视的短板。第一，递归深度是 O(log n)，虽然对普通链表来说没压力，但如果面试官严格要求 O(1) 空间，递归版不达标。第二，递归栈调用有额外开销，虽然不至于影响正确性，但在性能敏感的场景下，确实不如迭代版本利落。

所以在面试里，我一般先给递归版当主答案，主动说明它的空间代价，然后补一句"如果需要严格 O(1) 空间，可以用自底向上的迭代写法"，顺势展示第二套方案。这样既展示了基础功底，又展示了对工程细节的思考。

4. 迭代版自底向上：真正满足 O(1) 空间

4.1 思路来源：把小段有序段逐步合并

自底向上的归并排序，思路和递归版正好反过来。递归版是"先把链表拆到最小，再回头合并"；迭代版是"从一开始就假设每个节点是长度为 1 的有序段，然后两两合并，长度翻倍，直到合成一整条"。

举个例子，链表 4 -> 2 -> 1 -> 3。第一轮，步长 1，把相邻的两个节点两两合并：(4, 2) 合成 2 -> 4，(1, 3) 合成 1 -> 3，整条链表变成 2 -> 4 -> 1 -> 3。第二轮，步长 2，把 (2 -> 4) 和 (1 -> 3) 合并成 1 -> 2 -> 3 -> 4。结束。

关键点在于，每一轮都需要按照当前步长，把链表切成一段一段的，再把相邻两段合并。这个"按照固定长度切链表的动作"需要单独实现，这是迭代版比递归版多出来的部分。

4.2 完整代码

这里多了一个 cut 函数，它的作用是：从 head 开始往后走 n 个节点，切断并返回下一段的头节点。如果链表不够长了，就返回 nullptr。

class Solution { public: ListNode* sortList(ListNode* head) { if (!head || !head->next) return head; // 先求链表总长度，决定外层循环的轮数 int len = 0; ListNode* p = head; while (p) { len++; p = p->next; } ListNode dummy(0); dummy.next = head; // step 表示当前有序段长度，从 1 开始每轮翻倍 for (int step = 1; step < len; step <<= 1) { ListNode* prev = &dummy; ListNode* cur = prev->next; while (cur) { // 切出左段和右段，同时记录下一轮的起点 ListNode* left = cur; ListNode* right = cut(left, step); cur = cut(right, step); // 合并两段，接在已排好部分的后面 prev->next = merge(left, right); while (prev->next) prev = prev->next; } } return dummy.next; } ListNode* cut(ListNode* head, int n) { ListNode* p = head; while (--n && p) p = p->next; if (!p) return nullptr; ListNode* nxt = p->next; p->next = nullptr; return nxt; } ListNode* merge(ListNode* l1, ListNode* l2) { ListNode dummy(0); ListNode* p = &dummy; while (l1 && l2) { if (l1->val <= l2->val) { p->next = l1; l1 = l1->next; } else { p->next = l2; l2 = l2->next; } p = p->next; } p->next = l1 ? l1 : l2; return dummy.next; } };

外层循环的终止条件是step < len。因为每一轮步长翻倍，当 step 大于等于链表长度时，整条链表已经是一个有序段了。比如 len 是 4，step 依次取 1、2，然后 step 变成 4，循环结束，正好两轮。

4.3 三个容易理解错的点

迭代版写起来比递归版容易出细节问题，我挑三个最容易理解错的点讲。

第一个是 cut 函数里while (--n && p)的写法。有人会写成while (n-- && p)或者while (n && p) { p = p->next; n--; }。区别在于，我们要的是"走 n 步之后停在第 n 个节点"，而不是"走 n-1 步"。n 表示这段的长度，cut 返回的是第 n 个节点后面的部分。如果 n 是 1，就不需要移动，直接切掉第一个节点的后继；如果 n 是 2，才需要移动一步。--n是先减后用，先判断减完是否为 0，正好能让 p 停在第 n 个节点上。这个语义搞错了，切出来的段长度就是错的。

第二个是cur = cut(right, step)的时机。必须先切 right 再更新 cur，因为一旦切了 right，原链表的结构就变了。如果你先拿 cur 记录下一段起点，再去切 right，逻辑上没问题；但如果你先切了 right 而不记录，下一轮循环就找不到入口了。顺序错了，链表会丢一段，输出结果就缺了节点。

第三个是合并后while (prev->next) prev = prev->next;的作用。合并完两段之后，prev 要移动到合并结果的末尾，这样下一组合并才能接到正确的位置。这个移动是必要的，因为合并后的链表长度是 2 倍的 step，prev 如果停在原地，下一次 merge 的结果就会覆盖掉之前的成果。很多迭代版实现跑出来的结果是"只有最后一组排好序"，问题就出在没移动 prev。

5. 我踩过的坑和排查清单

5.1 快慢指针的边界细节

快慢指针最经典的坑是循环条件写错。两种常见写法分别是：

// 写法一：fast 从头出发 ListNode* fast = head; while (fast->next && fast->next->next) { slow = slow->next; fast = fast->next->next; } // 写法二：fast 从 head->next 出发 ListNode* fast = head->next; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }

两种写法都能找到中点，但 mid 的落点不同。写法一的 slow 落在中间偏右的位置（右半段的第一个节点），写法二的 slow 落在中间偏左的位置（左半段的最后一个节点）。我推荐写法二，原因前面说过：它保证左半段至少有一个节点。

有个细节必须注意：写法一里fast->next和fast->next->next都可能在循环里被访问，所以必须用fast->next && fast->next->next同时判空。少判一个，节点数为偶数的输入就能让你当场段错误。

5.2 迭代版最容易错的三处

迭代版除了上面讲的 cut 和 prev 问题，还有一个高频错误：切段时没处理"最后一段长度不够"的情况。比如链表长度是 5，step 是 2，切完两段后还剩最后一个节点，此时 cut(right, step) 返回 nullptr，但 left 段只有一个节点。这个场景是合法的，merge 函数要能处理 left 非空、right 为空的情况。也就是说，merge 里的 while 循环结束后，p->next = l1 ? l1 : l2;这行必须存在且正确，否则剩余节点会丢。

还有一个小坑是链表长度怎么求。直接在原链表上遍历求 len 没问题，但求完之后 head 没变，还指向原头节点。有人图省事用一个 p 变量遍历，遍历完 p 变成 nullptr，然后忘了 head 还在，直接把 p 拿去做后续处理，结果一切完蛋。记住：求长度用一个临时变量，后续操作还是用 head 或 dummy 的 next。

5.3 测试用例怎么设计

排序类题目的测试，我习惯分几个维度做：

边界类：空链表[]、单节点[1]、长度 2 的[1,2]和[2,1]。这三个用例能筛掉一大半的边界错误。

常规长度：[4,2,1,3]、[5,1,9,4,7]，手动推一遍结果再跑，能验证逻辑正确性。

重复元素：[3,3,1,2,3]。重复元素最容易暴露 merge 函数里的等号问题。如果 merge 里写的是l1->val < l2->val而不是<=，遇到相等的值就会不稳定，虽然不影响排序正确性，但不符合工程上对稳定排序的预期。

大长度：造一个 10000 节点的链表，验证性能和递归深度。递归版在超长链表上虽然理论上没问题，但某些平台的递归栈限制可能导致爆栈，这也是我为什么推荐面试时至少展示迭代版的原因。

对拍验证：写一个辅助函数，把链表转成 vector，用标准库 sort 排一遍，再转回链表，和 sortList 的结果逐节点比较。这是最省心的验证方法，能自动跑大量随机用例，比自己肉眼检查靠谱得多。

6. 这一步之后还能带走什么

6.1 快慢指针的扩展应用

把这道题吃透之后，你会发现快慢指针这个技巧在链表题里几乎无处不在。查找链表中间节点、判断链表是否有环、找到环的入口、找链表倒数第 k 个节点、判断回文链表，全都能用上它。

这些题目有一个共同模式：把一个需要"知道链表长度"的问题，转化成"用两个不同速度的指针"的问题。快慢指针的价值在于，它避免了先遍历一遍求长度的前置操作，让问题在单次遍历中就能解决。这个思维模式是通用的，做题时多往这个方向想，比死记模板有用得多。

还有一个收获是 "物理切断链表" 的意识。很多链表操作题（比如旋转链表、反转链表的一部分）都需要在特定位置切断，再重新拼接。排序链表这题的 cut 函数，其实就是这类操作的通用工具。下次遇到类似需求，可以直接把 cut 拿出来改改就用。

6.2 面试时怎么讲清楚这道题

面试如果遇到这道题，我的建议是按照"算法选型 -> 递归版本 -> 空间优化 -> 边界条件"这条线来讲。

先讲为什么选归并排序：链表不支持随机访问，快排的 partition 在链表上效率低且可能退化到 O(n²)，而归并的拆分和合并天然适合链表。这一段话就展示了你的算法分析能力。

然后给出递归实现，边写边解释快慢指针为什么这样初始化、为什么要切断、merge 为什么能处理剩余节点。写完了主动说一句"这个版本时间复杂度 O(n log n)，但递归栈占用 O(log n)，如果严格要求 O(1) 空间，我可以用自底向上的迭代版本"，然后给迭代版。

最后一定要主动谈边界：空链表、单节点、偶数长度、重复元素。面试官最怕听到候选人说"我的代码没问题"，你要自己先把边界情况摆出来。能主动暴露边界并给出处理方案的候选人，在面试官心里的印象分通常会高不少。

我个人在面试和实际工程中都验证过一句话：链表排序题，真正拉开差距的从来不是会不会写归并，而是能不能把切断和合并这两个动作做到滴水不漏。递归版练思路，迭代版练细节，两道都写熟了，这一题才算真正过关。

事后回顾这个题目，它更像是链表基本功的"综合大作业"。做之前你可能觉得自己快慢指针、合并链表都会了，做完才发现，原来每一个看似简单的技巧，落到实际代码里都有那么多讲究。把这些讲究都摸透了，再回头看其他链表题，你会明显感觉轻松很多。这也是值得收录进个人练习清单的题目之一。