企业官网建设流程全解析

LeetCode 148 排序链表是我第一次真正感受到"数组思维"和"链表思维"差距的题目。第一次刷这道题时，我的解法极其简单粗暴：遍历一遍链表，把所有节点值存进数组，调用 sort 排好序，再按顺序重建一条链表，测试用例稳稳全过。我差点以为这题已经结束了。直到有人问我"额外空间 O(n) 的排序，算不算满足题目的常数空间约束"，我才意识到，这道题真正要考察的从来都不是排序算法本身，而是你有没有理解链表这种数据结构。如果你也在刷这道题，或者准备面试时被这道题卡过，这篇内容会把递归归并、迭代归并、常见坑位和延展题目一次性讲清楚。

1. 题面就藏着一个大坑：常数空间的排序到底在考什么

1.1 原题要求拆解

LeetCode 148 的原题描述非常短：给你一个链表的头节点，请将它按升序排列，并返回排序后的链表。后面附了一句关键约束：在 O(n log n) 时间复杂度和常数级空间复杂度下完成排序。

前一个约束 O(n log n)，直接排除了冒泡、选择、插入这类 O(n²) 的排序算法。后一个约束"常数级空间"，才是整道题真正的分水岭。

常数级空间意味着你必须在原链表上通过改变节点之间的 next 指针来排序，不能靠数组、哈希表、优先队列或者新建链表来辅助。很多人第一反应是"把链表转成数组，sort 完再转回来"，这在逻辑上完全正确，测试也能过，可面试官只要追问一句"空间复杂度是多少"就会露馅——额外数组的 O(n) 空间明显不符合题意。

1.2 为什么"收集到数组再排序"不是正道

用数组辅助排序，本质上是拿空间换实现难度。它的时间确实是 O(n log n)，空间却是 O(n)。

也许你会觉得 O(n) 也没什么大不了，链表本来就要占 O(n) 空间了，多一个数组不也是 O(n) 吗？这里的区别在于，题面说的常数级空间，指的是算法额外申请的辅助空间不随输入规模增长。你额外开了一个和链表等长的数组，意味着链表越长，你额外用的空间就越多，这就不叫常数级空间。

而且从面试角度讲，这道题如果靠数组作弊，代码写起来没有任何难度，考察不出你对链表的理解。LeetCode 上的题解区也一直把这个解法当成反面教材。当然，如果你只是本地调试时想快速验证逻辑，用数组辅助也不是不行，但提交题解或者面试时，这不是正确的答案路径。

1.3 归并排序和链表的契合点在哪

O(n log n) 的排序算法里，快排、堆排、归并是三个主要选手。堆排需要数组的下标随机访问，链表要模拟堆的下标关系会非常别扭；快排可以用于链表，但后面我会单独说明为什么它不是最优解；剩下的归并排序，几乎是为链表量身定做的。

归并排序的核心动作有三个：把序列切分成两半、递归排序两半、合并两个有序序列。数组归并的痛点在于合并时需要临时数组暂存结果，空间 O(n)；链表归并完全不一样，合并两个有序链表只需要几个指针来回跳转，把节点重新串起来，不申请任何新节点。

举例来说，合并 [1,4,5] 和 [2,3,6] 这两个有序链表，你用两个指针分别指向两条链表的头，谁小就把谁接进结果链，然后移动对应指针。整个过程除了最终返回的头节点引用，只用了常数个指针变量。这就是归并排序和链表之间最天然的契合点：合并动作零额外空间。

2. 自顶向下归并：先把“切链表 + 合并有序链表”两个动作跑熟

2.1 快慢指针找中点的两个细节

自顶向下归并的第一步是找中间节点，使用的工具是快慢指针。慢指针每次走一步，快指针每次走两步，快指针走到头时，慢指针正好停在中间位置。

def get_mid(self, head): slow = head fast = head.next while fast and fast.next: slow = slow.next fast = fast.next.next return slow

这里有个很容易被忽略的细节：fast的初始值。常见的链表中间节点模板里，slow = head、fast = head，那是为了找"右中点"；但排序链表需要的是"左中点"。

如果fast = head，对于偶数长度的链表，比如 [1,2,3,4]，慢指针最后会停在 3，切分结果是 [1,2,3] 和 [4]，左侧比右侧多两个节点。再继续切下去，左侧的树会越来越深，整体递归深度可能从 O(log n) 退化到 O(n)，时间也跟着退化。

改成fast = head.next，同样处理 [1,2,3,4]，慢指针停在 2，切分成 [1,2] 和 [3,4]，两边均匀。奇数长度 [1,2,3,4,5] 时，慢指针停在 3，切分成 [1,2,3] 和 [4,5]，左边多一个节点，但递归深度依然是 O(log n) 量级。

找到中点后，必须立刻断链：

right_head = mid.next mid.next = None

顺序不能反。先保存mid.next到right_head，再把mid.next置空。如果先置空，后半段头节点就找不到了。

2.2 合并两个有序链表是地基

合并两个有序链表是 LeetCode 21，排序链表里的 merge 函数可以直接复用。需要注意，这里不能新建节点，只能改变 next 指针，把原本分散的节点重新串起来。

def merge(self, l1, l2): 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.next

虚拟头节点dummy在这道题里的作用是消除"结果链表的头节点到底来自 l1 还是 l2"的判断。没有 dummy，你需要单独写 if 判断第一次接入的是哪一边，代码会多出好几个分支。有 dummy 之后，统一把结果串到tail.next上，最后返回dummy.next，逻辑干净且不容易出错。

2.3 递归完整实现

有了get_mid和merge，递归归并的主体就四行：

class Solution: def sortList(self, head: ListNode) -> ListNode: if not head or not head.next: return head mid = self.get_mid(head) right_head = mid.next mid.next = None left = self.sortList(head) right = self.sortList(right_head) return self.merge(left, right)

递归退出条件是head为空或者只有一个节点。空链表和单节点天然有序，不需要排序。

手动走一遍 [4,2,1,3]：

• 第一次快慢指针找到中点 2，断成 [4,2] 和 [1,3]
• 递归排序 [4,2]，中点 2，断成 [4] 和 [2]，合并成 [2,4]
• 递归排序 [1,3]，中点 1，断成 [1] 和 [3]，合并成 [1,3]
• 最后合并 [2,4] 和 [1,3] 得到 [1,2,3,4]

整个过程典型的分治：先分解，后合并。

2.4 递归版的空间账

自顶向下归并的时间复杂度是 O(n log n)，空间复杂度是 O(log n)。这个 O(log n) 来自递归调用栈的深度，归并树有多少层，递归栈就有多深。

LeetCode 原题要求"常数级空间"，严格来说 O(log n) 不算常数级。很多题解把它当标准答案，面试时也能糊弄过去，但如果对面面试官扣字眼，让你"把空间真做到 O(1)"，那递归版就不满足了。

所以我的建议是：自顶向下用来理解思路、快速写对，但你要清楚它存在的问题。真要严格满足题面约束，看下面这版迭代归并。

3. 自底向上迭代归并：这才是常数空间的正主

3.1 从宏观看懂迭代归并的过程

数组版本的自底向上归并，大家应该都写过：先按长度为 1 的子数组两两合并，再按长度为 2、4、8……逐层合并，直到整个数组有序。

链表版本完全一样，只是把"按下标切子数组"换成"按步长切子链表"。

看一个直观的例子，链表 [4,2,1,3]：

• step = 1，合并每对长度为 1 的子链表：[4] 和 [2] 合并成 [2,4]，[1] 和 [3] 合并成 [1,3]，整个链表变成 [2,4,1,3]
• step = 2，合并每对长度为 2 的子链表：[2,4] 和 [1,3] 合并成 [1,2,3,4]

step 从 1 开始，每次翻倍。当 step 大于等于链表长度时，整个链表已经变成一条完整的有序链表，循环结束。

3.2 外层循环和内层循环的分工

先看完整代码：

class Solution: def sortList(self, head: ListNode) -> ListNode: if not head or not head.next: return head length = 0 cur = head while cur: length += 1 cur = cur.next dummy = ListNode(0) dummy.next = head step = 1 while step < length: prev = dummy cur = dummy.next while cur: left = cur right = self.split(left, step) cur = self.split(right, step) prev.next = self.merge(left, right) while prev.next: prev = prev.next step = step << 1 return dummy.next def split(self, head, step): if not head: return None cur = head for _ in range(step - 1): if not cur.next: break cur = cur.next right = cur.next cur.next = None return right def merge(self, l1, l2): 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.next

外层循环while step < length控制归并的轮数。step 是"已经有序的子链表长度"，一开始只有单节点有序，所以 step = 1。每完成一整轮，step 翻倍。

内层循环while cur负责把整个链表扫描一遍。每次内层循环做四件事：

1. left = cur：当前段起点
2. right = split(left, step)：把 left 切成一段长度不超过 step 的子链表，并返回后续部分的头
3. cur = split(right, step)：再把 right 切成一段长度不超过 step 的子链表，并返回下一轮的起点
4. prev.next = merge(left, right)：合并两段有序子链表，接到已经排好序的链表末尾

这里最关键的是 split 函数。它的作用是把head之后的第 step 个位置断开，让被切出来的子链表尾部变成 None，防止 merge 时顺着旧 next 指针串到其他节点。

prev指针的作用是串起每一段 merge 后的结果。第一轮循环时，prev 指向 dummy，所以第一个 merge 结果会接到 dummy 后面，同时更新了dummy.next，让它指向当前链表真正的头节点。之后 prev 通过while prev.next移动到这段合并结果的尾部，再继续接下一段。

3.3 虚拟头节点为什么在这里这么顺手

自底向上迭代里，每轮要做多次 merge，每次 merge 产出的头节点可能都不一样。

举例：step = 1 时，第一次 [4] 和 [2] 合并，头变成 2；第二次 [1] 和 [3] 合并，头变成 1。没有 dummy 的话，这一轮结束后，你必须记住这一轮的"新头"是哪一段的头，下一轮又得重新判断，代码会非常容易错。

有了 dummy，每次循环开始时prev = dummy，第一个 merge 结果直接接在 dummy 后面，后面每一段都通过 prev 串起来。最后返回dummy.next，就拿到了整个排序链表的头。

这种"虚拟头节点 + prev 游标"的组合，是所有涉及"把多个结果串成一条链"的链表题的通用套路。你会在区间反转、链表加法、合并 K 个链表里反复见到它。

3.4 自底向上的复杂度确认

时间上，每轮 step 都要从前往后完整扫描一遍链表，扫描过程就是一次次 split 和 merge，整体是 O(n)；step 从 1 倍增到 length，一共 O(log n) 轮，所以总时间 O(n log n)。

空间上，代码里只有dummy、prev、cur、left、right和 split 内部的cur等几个指针变量，没有递归栈，也没有额外数组，严格 O(1)。

这版才是真正满足 LeetCode 148 题面"常数级空间"要求的标准答案。如果你的面试官要求空间 O(1)，直接把这一版写给他看。

4. 链表排序的选型思考：为什么快排在链表上不香

4.1 数组快排和链表快排的差异

你可能会想，O(n log n) 的快排是不是也能用在链表上？可以，但不推荐。

数组快排的核心是 partition：选一个 pivot，通过随机访问把小于、大于 pivot 的元素放到两侧。数组的随机访问是 O(1)，所以 partition 很轻松。链表没有随机访问，想跳到任意位置只能遍历，这导致链表 partition 的常数巨大，而且还要解决"切完怎么再拼回去"的问题。

网上能搜到链表快排的实现，常见做法是：取头节点值作为 pivot，遍历链表把它拆成小于、等于、大于三条子链，递归排序小于和大于两条，最后按顺序拼接。听上去也不复杂，但致命问题在于最坏情况的退化。

如果输入链表已经有序，取头节点做 pivot，每次分割都会出现一边为空的情况。比如 [1,2,3,4,5]，pivot 是 1，大于部分的链表是 [2,3,4,5]，小于部分为空，递归深度直接变成 O(n)，时间复杂度退化为 O(n²)。这不是理论上的小事，在 LeetCode 上排序一条长链表，遇到有序测试用例时，快排会慢得离谱。

归并排序不受输入有序性影响，因为它永远从中间切分，递归深度稳定 O(log n)。稳定性、可预测性都更好，这就是链表排序选归并而不是快排的根本原因。

4.2 插入排序：能过但只适合特定场景

LeetCode 147 就是一道"对链表进行插入排序"的题，允许 O(n²) 时间，只要求你用插入排序实现。这道题对接近有序的链表表现很好，比如你有一个已经排好序只差一两个位置的数据。

但排序链表面对的输入是任意乱序，插入排序的节点移动次数会接近 n²/2，大数据量一定扛不住。面试时提到排序链表，默认不要把插入排序当主答案，除非面试官特意说"数据接近有序"或者"链表很短"。

4.3 一张表看排序算法在链表上的表现

面试时如果能说出这张表的信息，会显得你对排序算法选型有整体认识，而不是只会背代码。

5. 踩坑实录：断链、死循环、栈溢出都在这道题里出现过

5.1 快慢指针的 fast 初始化差一个 bug

我自己第一次写递归归并时，用的是很多"链表中间节点"通用模板里的fast = head。单独做找中点题没问题，但放在排序链表里很隐蔽。

用 [1,2,3,4] 走一遍就明白：

• fast = head时，第一轮循环 slow 走到 2，fast 走到 3；第二轮 slow 走到 3，fast 变成 None，循环结束。中点 slow 停在 3，切出的右段是 [4]，左段是 [1,2,3]
• 接下来递归 [1,2,3]，又会切出 [1,2] 和 [3]，递归树明显一边倒
• 链表越长，这种不平衡越严重，时间从 O(n log n) 往 O(n²) 退化

把fast改成head.next后，[1,2,3,4] 先切成 [1,2] 和 [3,4]，[1,2,3,4,5] 切成 [1,2,3] 和 [4,5]，递归树就均衡了。

这个快慢指针初始化的细节，和 LeetCode 876 的考点不一样。876 找中间节点怎么找都能过，但排序链表里这个选择会直接影响复杂度。建议直接记结论：排序链表用fast = head.next。

5.2 递归不断链，合并会串链

找完中点不mid.next = None，是另一类经典错误。

想象一下，mid 停在中点，你拿到right_head = mid.next后没断开，然后就递归调用了。递归排序左半段时，左半段尾节点和右半段还是连着，merge 两个子链表时，tail 指针就会顺着旧 next 跑到右半段里去，最后结果链表可能出现环。

LeetCode 的测试结果一般不是"答案错误"，而是直接报 cycle detected。遇到这个报错，第一件事就检查是不是哪个next没断开。

断链操作的顺序我也强调一下：right_head = mid.next和mid.next = None顺序不能反。先保存右半段头，再断开，这条逻辑要形成肌肉记忆。

5.3 自底向上里的 split 切割时机

迭代归并里，90% 的 bug 都出在 split 函数。

常见的错误写法：

def split(self, head, step): cur = head for _ in range(step - 1): cur = cur.next right = cur.next cur.next = None return right

如果 head 后面不够 step 个节点，cur会走到链表尾部的 next，也就是 None，下一步cur.next直接抛空指针异常。加上if not cur.next: break，这一步才能兜住末尾短段的情况。

另外，split 里断链的时机非常讲究。切 left 的时候，只有当 left 的长度大于等于 step 时，cur.next才一定非空；如果 left 正好是链表最后一段，长度不足 step，cur.next本来就是 None，赋不赋值看不出来，但逻辑上依然要执行cur.next = None，保持行为一致。

我第一次写迭代归并，split 里忘了把 left 尾部断开，结果 merge 的时候，tail 指针合并完 left 就顺着 next 跳进了 right 的区域，某些节点被跳过去，输出顺序完全错乱。排查了整整一下午。自底向上版本对"切一段、断一段"的要求比递归版严格得多，写完后强烈建议用 [2,1,4,3] 这种长度短的用例单步调试一遍。

5.4 用这些测试用例验证正确性

我每次写完链表排序，都会建一套本地用例：

• 空链表：head = None，返回 None
• 单节点：head = ListNode(1)，返回原节点
• 两个节点且逆序：[2,1]，验证 merge
• 三个节点：[3,2,1]，验证分解
• 四个节点：[4,2,1,3]，验证偶数长度中点
• 长逆序：[5,4,3,2,1]，验证整体排序
• 重复元素：[2,1,2,2]，验证相等节点处理
• 已经有序：[1,2,3,4]，验证不会越排越乱
• 负数混排：[3,-1,-5,0,2]，验证负数比较

跑完这组用例再去 LeetCode 提交，能少踩很多坑。

6. 这道题带出来的刷题地图

6.1 它是由哪些基础题拼起来的

排序链表不是一个孤立知识点，它本质上是三道基础题的组合：

• LeetCode 21 合并两个有序链表：merge 函数原封不动
• LeetCode 876 链表的中间结点：快慢指针找中点，注意 fast 初始值的选择
• 链表遍历和虚拟头节点：链表题的通用基本功

如果你能把这三件事做得滚瓜烂熟，面试现场完全可以现场推导出排序链表的主框架。真正需要额外想清楚的只有两个点：递归还是迭代，以及空间怎么控制。

6.2 从 148 你能延伸去做的进阶题

刷完排序链表之后，这几道题会突然变得简单很多：

• LeetCode 23 合并 K 个升序链表：用分治归并，或者优先队列，和 148 的归并思想一脉相承
• LeetCode 147 对链表进行插入排序：做这道题时，你自然会更清楚为什么排序链表不选插入排序
• LeetCode 143 重排链表：要求 L0 → Ln → L1 → Ln-1 → L2 → ...，需要用到快慢指针找中点、反转后半段、穿插合并，这三步全是 148 练过的动作
• LeetCode 148 的变体：如果面试官限定只能修改 next 指针，不能修改节点 val，那就必须写迭代归并，因为递归归并虽然也没改 val，但空间不满足

我刷题时有句自己的总结：链表题做到最后，你会发现自己其实就靠几招——快慢指针、虚拟头节点、反转链表、合并链表。排序链表是把这几招揉在一起考你的综合题。

6.3 我的刷题心得与面试表述建议

排序链表这道题我真的前后刷了三遍，第一遍数组作弊，第二遍递归归并能过提交但被空间复杂度问住，第三遍才老老实实把自底向上写熟。现在让我写这道题，我的固定顺序是：

1. 说思路：链表没有随机访问，优先考虑归并排序；递归版空间 O(log n)，迭代版 O(1)，题目要求常数空间所以我用迭代版
2. 先写 merge，因为它是地基
3. 再写 split，注意断链
4. 最后拼主循环，用 dummy 和 prev 串结果

这个表达顺序的好处是，面试官每看一个函数都能明白你在干什么，不需要等你把所有代码写完再猜你的思路。

最后分享一个小技巧：写链表题时，把所有功能拆成独立的小函数，get_mid 只管找中点，split 只管切段，merge 只管合并，不要在 sortList 里把逻辑全挤在一起。这样调试方便，面试时讲述也清楚。等你把这些小函数写顺手了，排序链表这题基本就是默写。