企业官网建设流程全解析

排序链表这题，LeetCode第148题，可以说是我在热门100题里刷得最揪心的一道。解法逻辑并不绕，就是归并排序那一套分治思想，但真到自己上手写的时候，断链、死循环、空指针各种小毛病轮着来，我第一次写完整花了四十多分钟，最后还带着一个隐蔽bug。后来反复练了几遍，才把递归和迭代两种版本都吃透。这篇文章就是把我从卡壳到写顺的全过程整理出来，思路怎么定的、代码怎么拆的、都有哪些坑，一次性讲透。你不用怕链表基础差，我尽量用最直白的话把每个细节说清。

1. 题目拆解：排序链表到底在考你什么

1.1 两个被反复强调的硬性要求

题目本身一句话就能说完：给你一个链表的头节点 head，把它按升序排序，然后返回排序后的链表。

但真正决定考察难度的，是后面这两条限制：

• 时间复杂度要求 O(n log n)
• 额外空间复杂度要求 O(1)

如果你不常刷链表题，可能觉得这要求不算苛刻。但我们只要往深想一步就会发现，这道题几乎把“数组时代”的排序捷径全堵死了。你可以先回想一下，对数组排序，手写快排、调用库函数，怎么着都行。可一旦把数组换成链表，事情就不一样了，链表节点只能通过 next 指针单向访问，没有下标，没有随机访问能力，这意味着很多在数组上非常順手的操作在链表上根本做不了。

所以这道题表面考的是“排序”，实际考的是三件事：你对分治思想的理解深度，你对链表指针操作的熟练程度，以及你在复杂约束条件下选择算法的判断力。LeetCode上这道题的讨论区非常热闹，原因也在于此——它是一道能拉开差距的题目，很多人一看就会，一写就废。

1.2 为什么常见的排序算法在这里集体失灵

先帮大家把几个“看起来可行，实际行不通”的路线过一遍。这不仅仅是做题，更是以后面试里别人追问你“为什么不用XX排序”时的弹药。

插入排序：时间复杂度最坏 O(n^2)。虽然链表实现插入排序很简单，不需要搬移元素，只要找到插入位置改指针就行，但题目明确要求 O(n log n)，所以直接出局。顺带一提，LeetCode第147题“对链表进行插入排序”就是专门让你练这个的，可以作为反面教材做一遍。

快速排序：很多人第一反应是快排。问题是快排的灵魂在于 partition 操作，它需要两个指针从两端往中间逼近，依赖的是数组的随机访问能力。链表是单向的，你只能从头往后遍历，虽然可以硬写一个链表版的 partition，但每次都要从头扫描，指针管理极其繁琐，而且最坏情况时间复杂度依然会退化到 O(n^2)。这种解法在面试里属于“能说出口，但不推荐”。

堆排序：堆排序的时间复杂度稳定在 O(n log n)，空间复杂度也能做到 O(1)，看起来完美。可问题是，堆这种数据结构天然是用数组实现的，你需要在 O(1) 时间内访问堆顶和交换元素。链表无法做到这些，除非你先把链表转成数组，那额外空间就是 O(n) 了，不符合要求。

取巧方案：还有一种看着很“聪明”的做法，遍历链表把所有 val 收集到一个数组里，用 Arrays.sort 或者快速排序排完序，再从头遍历链表把值写回去。时间复杂度是 O(n log n)，代码也短，但它额外用了 O(n) 的空间。LeetCode 官方明确要求 O(1) 空间，所以在严格意义上不算过关。网上有些题解会提这种方法，面试时你当成思路聊一句可以，千万别当主方案讲。

把这些方案排除完之后你会发现，剩下的最优解基本就只有一个方向：归并排序。归并排序的分治思想和链表的结构简直是天作之合。一个链表的拆分，只需要找中点然后断开 next 指针就行了；两个链表的合并，只需要不断比较头节点、把较小的节点串起来就行了，整个过程不需要随机访问，不需要来回移动指针，每一步都是顺手的事。

2. 思路定型：归并排序天然契合链表结构

2.1 先回忆一下归并排序到底是怎么运作的

归并排序是最典型的分治算法，一次完整的排序分三步走：

1. 把当前序列从中间分成左右两个子序列
2. 递归地对左右两个子序列分别排序
3. 把两个已排序的子序列合并成一个完整的有序序列

从宏观上看，它就是把“排序”这个复杂任务，拆成了“切一半，各自排好，再合并”这三个简单操作。重复这个步骤直到每个子序列只剩一个元素，此时子序列天然有序，然后逐层合并回去，整个序列就有序了。

对数组做归并排序时，你还需要一个临时数组来存放合并结果，所以经典的数组版归并排序空间复杂度是 O(n)。这是它的短板。但链表不一样，链表的合并只需要改 next 指针，不需要额外的数据存储空间，所以链表的归并排序可以把额外空间压得非常低。这个特性，让归并排序从“可用”变成了“首选”。

2.2 两种实现路线：自顶向下和自底向上

同样是归并排序，落到链表上有两种实现思路，面试时这两个版本最好都掌握。

自顶向下（递归版）：先找链表的中点，把链表切成前后两半，递归排序左右两半，最后把两个有序链表合并起来。这个版本写起来更符合人的直觉，代码结构清晰，也是绝大多数题解最先给出的方案。唯一的代价是递归需要栈空间，递归深度是 O(log n)，所以严格来说额外空间是 O(log n)，不是 O(1)。

自底向上（迭代版）：不递归，而是从长度为1的子链表开始，两两合并，得到长度为2的有序子链表；再两两合并，得到长度为4的有序子链表；如此反复，直到整个链表有序。整个过程只需要几个指针变量，额外空间是 O(1)，完美契合题目 Follow up 里的 constant space 要求。

你可能会问：既然递归版更简单，我掌握递归版不就行了？这里要想清楚两件事。第一，LeetCode 这道题的 Follow up 明确问了能不能用 O(1) 空间完成排序，如果你只写递归版，被追问到空间复杂度时容易卡壳。第二，不少大厂面试官会专门让你把递归改成迭代，考察你能不能跳出递归的舒适区，用循环控制状态。所以我的建议是：先写递归版把思路理通，再花时间把迭代版啃下来。

3. 手把手实现：自顶向下归并排序的完整代码

3.1 核心步骤一：快慢指针精准找中点

自顶向下归并排序的第一步，是把链表从中间切开。链表不像数组，你没法直接算下标取中位数，只能借助快慢指针。

快慢指针的思路很朴素：慢指针 slow 每次走一步，快指针 fast 每次走两步。当快指针到达链表末尾时，慢指针刚好停在链表的中间。但这里有一个细节非常关键，也是很多人在这个步骤上翻车的根源——快慢指针的初始位置。

我这里直接给出我的写法，配合链表长度各异的场景来理解：

private ListNode getMid(ListNode head) { ListNode slow = head, fast = head.next; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } return slow; }

注意 fast 初始化的是 head.next 而不是 head。这样做的目的是让 slow 在链表长度为偶数时落在中间偏左的位置，也就是左半部分的最后一个节点。

举个例子，链表是 1 -> 2 -> 3 -> 4，如果 fast 也初始化为 head，slow 最后会停在节点3，你把它当成中点断开，左半部分就变成了 1->2->3，右半部分只剩 4，切分不均匀倒还好，关键是递归时容易出现左右两边长度分配混乱，或者死循环。而 fast 初始化为 head.next，slow 会停在节点2，左半部分是 1->2，右半部分是 3->4，干净利落。

拿到中点之后还有一件事必须立刻做：把前半段的尾巴断开。也就是 mid.next = null。这一步不能省，省了你后面 sortList 递归的时候，左右两个子链表还藕断丝连，合并的时候链表里容易出现环，提交上去就是死循环超时。

3.2 核心步骤二：递归拆分与有序合并

找完中点并断链之后，整个链表被分成了前后两个独立子链表。把这两个子链表分别扔给 sortList 递归处理，等它们各自返回有序链表后，再进行合并。合并操作就是我们熟悉的 merge 两个有序链表，用 dummy 节点简化头部的空指针判断：

private ListNode merge(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(-1); ListNode cur = dummy; while (l1 != null && l2 != null) { if (l1.val <= l2.val) { cur.next = l1; l1 = l1.next; } else { cur.next = l2; l2 = l2.next; } cur = cur.next; } cur.next = (l1 != null) ? l1 : l2; return dummy.next; }

merge 的逻辑不复杂，核心就是两个指针分别指向两个链表的头节点，谁小就先接谁，接完之后指针往后移一位。这里有一个容易被忽略的点：比较的时候用的是小于等于，也就是 l1.val <= l2.val 时优先接 l1 的节点，这个细节保证了排序的稳定性。如果一边已经为空了，直接把另一边的剩余链表整体接上就行，因为剩余部分已经是有序的。

主函数 sortList 就三段式，递归终止、中点断开、左右合并：

public ListNode sortList(ListNode head) { if (head == null || head.next == null) { return head; } ListNode mid = getMid(head); ListNode rightHead = mid.next; mid.next = null; ListNode left = sortList(head); ListNode right = sortList(rightHead); return merge(left, right); }

整体逻辑非常清爽：链表只剩一个节点或者为空，直接返回；否则找到中点并断开，递归处理左右两半，最后合并返回。这一段代码的线条很干净，建议你手写至少三遍，第一遍对着看，第二遍不看写，第三遍看能不能顺手写出边界条件。

这里提一下时间复杂度：每层递归都需要完整遍历一次链表的所有节点，递归树的高度是 O(log n)，所以总时间复杂度是 O(n log n)。空间方面，递归调用会占用栈空间，深度是 O(log n)，这就是前文提到的，它不是严格的 O(1) 空间。

4. 进阶实现：自底向上归并排序，真正的O(1)空间

4.1 为什么说迭代版才是这道题的完全体

递归版写起来舒服，但面试官一句“你能把额外空间降到 O(1) 吗”，立马就会把人问住。因为递归调用本身的栈空间不是常数级，无论你怎么优化语句，深度始终是 O(log n)。如果你面对的是严格要求 constant space 的场景，就必须请出自底向上的迭代版归并排序。

自底向上的核心思想，是把“递归切分”这一步完全去掉，改成从最小单元开始合并。具体做法是：先把链表看成一个个长度为 1 的“天然有序子链表”，第一轮两两合并，得到若干个长度为 2 的有序子链表；第二轮再两两合并，得到长度为 4 的有序子链表；每轮把子链表长度翻倍，直到合并后的长度超过链表总长度，整个链表就自然有序了。整个过程只用到有限的几个指针变量，额外空间 O(1)，时间依然是 O(n log n)。

这个思路的难点在于：递归版里，子链表之间的边界全靠递归天然分割，而迭代版里，你必须自己手动控制“切到哪里为止”,也就是需要一种操作，能把一个长链表按指定长度切下一段来。

4.2 cut函数：按指定长度切分链表的利器

我们定义一个剪断函数 cut(head, n)，表示从 head 节点开始，切下前 n 个节点，然后返回剩余链表的头节点。切下来的这段，末尾的 next 会被置为 null，和后面的部分彻底断开。

private ListNode cut(ListNode head, int n) { ListNode p = head; while (--n > 0 && p != null) { p = p.next; } if (p == null) { return null; } ListNode next = p.next; p.next = null; return next; }

这个函数看起来短，理解起来需要一点耐心。它做的事情是：先让指针 p 沿着链表走 n-1 步，也就是从 head 走到第 n 个节点；然后记录 p.next 为 next，再把 p.next 置为 null，相当于把第 n 个节点之后的链条剪断；最后返回 next，next 就是剩余链表的头。如果链表长度不足 n，说明没有剩余节点了，那 p 会走到 null，函数返回 null。

举个例子，链表是 A -> B -> C -> D，调用 cut(head, 2)，p 先走到 B，然后把 B.next 置为 null，返回 C。此时 A -> B 是一段独立链表，C -> D 是剩余链表。这个动作就是迭代版归并排序里最核心的基本操作。

4.3 完整代码与逐段拆解

有了 cut 函数，再配合之前写好的 merge 函数，自底向上版本的主逻辑就能拼起来了：

public ListNode sortList(ListNode head) { if (head == null || head.next == null) { return head; } int length = 0; ListNode node = head; while (node != null) { length++; node = node.next; } ListNode dummy = new ListNode(-1); dummy.next = head; for (int subLength = 1; subLength < length; subLength <<= 1) { ListNode prev = dummy; ListNode cur = dummy.next; while (cur != null) { ListNode head1 = cur; ListNode head2 = cut(head1, subLength); cur = cut(head2, subLength); prev.next = merge(head1, head2); while (prev.next != null) { prev = prev.next; } } } return dummy.next; }

我来逐段拆解这段代码。第一段先计算链表总长度，这个是为了让外层循环知道最多要合并到多大的子链表为止。dummy 节点指向原始头节点，它会在每一轮合并中，帮我们记录合并后的新的链表头。

外层 for 循环是最重要的一层，subLength 从 1 开始，每轮翻倍。每一轮，我们都要把整个链表从头到尾遍历一遍，把链表分割成多个长度为 subLength 的子链表，让相邻的两两合并。循环结束条件 subLength < length，意思是当子链表长度已经不小于总长度，说明整个链表已经是一整段有序链表了，不需要再合并下去。

内层 while 循环负责真正的一轮合并。prev 指向合并结果的尾部，cur 指向当前待处理段的起点。循环体里连续两次调用 cut，第一次把 cur 所在的链表切下 subLength 个节点作为 head1，第二次把剩余部分再切下 subLength 个节点作为 head2。如果链表已经被切空，cur 会变成 null，内层循环自然退出。

接下来把 head1 和 head2 合并，接到 prev.next 上。这里非常关键的一个细节是，prev 必须时刻指向“已经合并完成的链表的末尾”。所以每次合并完，要写一个 while 循环让 prev 一直往后移动，直到走到 null 前一个节点，也就是刚刚合并完的那段链表的末尾，这样下一次合并结果才能正确拼接上去。

这里可能有人会问：那如果 head2 在 cut 的时候返回了 null，也就是说剩余链表不够一段 subLength 了，merge(head1, null) 会返回什么？答案是直接返回 head1，相当于这段没有和谁合并，原样保留。这没有问题，因为当剩余子链表长度不足 subLength 时，它本身已经是有序的，不需要再和空链表合并。后面如果还有更长的合并轮次，它自然会作为完整的一段参与下一轮。

迭代版的思想比递归版难理解一些，我建议你拿一个短一点的链表，比如 4 -> 2 -> 5 -> 1 -> 3，在纸上模拟一遍这个流程，感受一下 subLength 从 1 变 2 变 4 时，链表的形态如何一步步变得有序。画完一遍之后，代码里的每个指针作用都会清晰很多。

5. 避坑指南：写这道题最容易翻车的5个细节

5.1 致命死循环：忘记断链的后果

我见过最多的错误，是找完中点后没有把 mid.next 置为 null。递归排序左右两半时，左半边链表的尾节点仍然指向右半边链表的头节点，两个子链表在物理上是连着的。sortList 递归处理左半边时，又去找中点，又去递归，左半边里永远包含右边的内容，整个递归过程就会无限进行下去，最后要么栈溢出，要么超时。

我记得自己第一次写这题，代码逻辑看着完全没问题，但提交就是 Time Limit Exceeded。后来在本地调试，打印链表内容才发现，递归到某一层时链表根本没变小，问题就出在这条断链上。所以每次找完中点，我会条件反射地写一行 mid.next = null，这个习惯比记任何结论都管用。

5.2 边界条件：空链表和单节点链表要最先处理

sortList 函数的递归终止条件，也就是 head == null || head.next == null 这一句，必须放在最前面。很多人会因为题目示例里链表都至少有多个节点，就忽略这个问题。但面试时，面试官偏偏就喜欢递上一个空链表测你。这两个条件缺一不可：head == null 处理空链表，head.next == null 处理只有一个节点的链表。少了任何一个，递归调用就可能出现空指针异常。

5.3 快慢指针初始化：奇偶长度的差异

快慢指针找中点，慢指针停在哪个位置，取决于快指针是从 head 还是 head.next 出发。我在 3.1 小节里强调过，推荐用 fast = head.next，让慢指针在偶数长度时停在左半部分最后一个节点。如果你习惯用 fast = head，也不是绝对不行，但你要额外用一个 prev 指针记录慢指针的前驱节点，然后在断链时用 prev.next = null 来切分，代码会多出一个变量，逻辑也没那么直观。

两种写法我都试过，最终选择了 fast = head.next 的版本，因为它的断链动作最顺：拿到 mid 后直接 mid.next = null，不需要额外记录前驱。

5.4 自底向上：prev指针的移动时机

迭代版最容易错的地方不是 cut，而是 prev 指针维护。merge 结束后，prev.next 被指向合并后的链表头部，但 prev 本身还停在原来的位置，必须用 while (prev.next != null) prev = prev.next 把 prev 推到合并链表的末端，下一轮才能继续在后面接新的合并结果。如果你漏掉这一步，下一轮合并完的链表会被接到错误的位置，结果就是排序后的链表七零八落。

有人可能会想：能不能用 prev = tail 这种方式直接记录每次 merge 的尾节点？理论上可以，但 merge 函数返回的是头节点，拿尾节点还得再遍历一遍，反而不如 while 循环来得简洁。这里没有太多花哨技巧，重点是别忘。

5.5 常见错误速查表

为了方便你自查，我把几种典型错误的症状、原因和解决方案整理成一个表格：

这个表格其实覆盖了我刷这道题以及看别人代码时遇到的大部分问题。你在本地写代码的时候，可以把这个表贴在旁边，跑测试用例之前先自己对照检查一遍。

6. 面试延伸：从排序链表引出的一串题目

6.1 一个模板打天下：相关题目清单

排序链表这道题的解法里，有两个函数是高频复用的：merge 两个有序链表，以及快慢指针找链表中间节点。这两个动作几乎是 LeetCode 链表题的“通用积木”，单独拿出来都各自对应一道经典题目。

• 合并两个有序链表（LeetCode 21）：就是本题的 merge 函数。你把排序链表做完，这道题基本等于白送。
• 链表的中间节点（LeetCode 876）：就是本题的 getMid 函数。注意876题没有断链的要求，只要返回中间节点即可，但找法的思想和本题小程序一样。
• 合并K个升序链表（LeetCode 23）：可以用两两合并的方式实现，而两两合并的核心还是这个 merge 函数。更进阶的解法是配一个优先队列，但建议先把两两合并写熟。
• 对链表进行插入排序（LeetCode 147）：这就是我在第1节里提到的反面教材。做完排序链表，再去做147题，你会对两种排序思路的差异有更直观的感受。
• 重排链表（LeetCode 143）：这道题需要先找中点，再反转后半部分，最后交错合并两条链表，每一步都是前面那些题里拆出来的基础操作。很多人刷完排序链表去刷143会异常轻松，因为找中点和合并这两个基本功已经被反复打磨过好几遍了。

把这些题目放到一起刷，你会发现所谓的“刷题”，其实是在反复使用几个核心模式。当你能把 merge 和 getMid 写得不用过脑的时候，链表的绝大多数难题就都有了基本骨架。

6.2 再深入一点：面试官还可能追问什么

排序链表这道题本身不难，但它上面的追问可以很有深度。我在面试中被问过两个印象很深的问题，这里分享一下。

第一个问题：如果这道题不限制空间复杂度，你会怎么做？答案就是取巧方案，遍历收集所有节点的 val 到数组，排序，再写回链表。这个方案的代码量远小于归并排序。但面试官的考察点其实是在试探你，看你知不知道归并排序为什么是最优解，以及能不能在限制条件下放弃“简单方案”切换思路。所以哪怕你面试时先答了取巧方案，也一定要立刻补充一句：这只适合没有空间限制的情况，严谨的解法是归并排序。

第二个问题：归并排序是稳定排序吗？你的 merge 函数里用小于等于会不会破坏稳定性？答案是稳定的。关键在于当两个链表头部节点的值相等时，我们优先取左半边的节点，这样就保证了相等元素的相对位置不变。这在某些有特殊排序需求的场景中是一个实打实的加分项。

刷完这道题之后，我对链表题的心态变了很多。以前总想着靠背代码来应付，现在更习惯先想清楚“断链之后怎么接回来”“递归到多深”这些本质问题。尤其是画图这件事，我强烈建议你准备一支笔和一张草稿纸。链表题和数组题最大的不同就在于：数组的索引变化是隐性的，而链表的每个节点指向关系都是显性存在的，不画图全靠脑补，指针一旦多起来就很容易乱。我后来能把两种版本的代码都写得又快又稳，核心原因就是从第一遍画图开始，把每一轮断链、连接都落到实处了。

最后再分享一个实用小经验：面试写这题的时候，如果你先写递归版，可以在代码写完之后主动告诉面试官，说你知道递归版本的空间复杂度是 O(log n)，并可以立刻改写成 O(1) 空间的迭代版本。这一句话既证明了你对空间复杂度的敏感度，又展现了你对递归和迭代两种实现掌握的熟练度，效果往往比单纯把代码写对要好得多。