排序链表全解析：归并排序的递归与迭代实现

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

1.1 原题要求与核心考点

先把题目摆出来：给定一个单链表的头节点head，要求对它进行排序，返回排序后的链表。进阶要求是时间复杂度O(n log n)，空间复杂度O(1)（常数额外空间）。

很多人第一次看到这题会想：这不就是给数组排序换了个容器吗？直接遍历链表把值取出来，排好序，再重新串回去不就行了？确实能过，但面试官只要追问一句"如果不允许改动节点值，必须通过调整指针来完成排序呢？"就会当场卡住。所以这题真正考的不是"会不会调用Arrays.sort()"，而是你对链表这种数据结构的理解深度，以及对归并排序、快速排序、堆排序等经典算法在非连续内存结构上的适配能力。

核心考点可以拆成三层：

• 第一层：能不能识别出题目要求的时间复杂度约束。看到O(n log n)，脑子里要立刻排除冒泡、插入、选择这类O(n^2)的排序。
• 第二层：能不能在链表上实现归并排序。关键操作是"找中点"（快慢指针）、"合并两个有序链表"（经典双指针），这两个子问题单独拎出来都是 LeetCode 简单题，但组合起来就是中等偏上的难度。
• 第三层：能不能处理空间复杂度限制。递归写法虽然直观，但递归调用栈需要O(log n)的额外空间，严格来说不满足进阶要求。想要真正做到O(1)空间，得用自底向上的迭代归并。这一层能筛掉很多人。

1.2 为什么这题是面试高频题

LeetCode 热门 100 题里，排序链表一直占着位置不是偶然的。我面试过不少候选人，链表这块大家普遍会写反转、会写环形链表检测，但一遇到"排序"这种需要对链表结构进行改动的题目，很多人就露馅了。原因在于：数组排序是"读-写-改"三个动作，而链表排序本质上是"拆-合-接"的指针游戏。你不仅要会排序，还得保证在拆解和合并的过程中不丢节点、不成环、不越界。

另外，这题也是 LeetCode 148 题，是很多公司笔试和面试的高频题。它作为一个"中间难度"的题目，既能考察基础（递归、指针、链表操作），又能考察进阶（迭代归并、空间复杂度分析），非常适合做面试筛选题。如果你在 LeetCode 每周赛里做到类似题目，排序链表的核心思路往往可以作为前置技巧直接复用。

2. 方案选型：为什么归并排序是首选

2.1 常见排序算法在链表上的命运

先过一遍经典排序算法在链表上的表现。冒泡排序和插入排序，时间复杂度O(n^2)，虽然实现简单，但直接不符合题目要求。选择排序每次找最小值需要遍历未排序部分，同样是O(n^2)，而且频繁交换节点反而更慢。堆排序理论上能做到O(n log n)，但链表不支持随机访问，建堆过程会比较别扭，而且需要额外的指针数组或容器，空间也上去了。快速排序的原地分区依赖双指针从两端向中间移动，这在数组上很顺手，但是在单链表上你只能单向移动，实现起来非常绕，后面第三节我详细说。

那么剩下的就是归并排序。归并排序天然适合链表，因为它不依赖随机访问，只需要递归地把链表拆分成两半，分别排序后合并即可。合并两个有序链表时，只需要比较两个链表的头节点，把较小的那个摘下来接在后面，整个过程只需要O(1)额外指针，完全不需要额外数组。所以"链表 + 归并排序"是时间复杂度和空间复杂度都最优的组合。

2.2 归并排序的自顶向下 vs 自底向上

归并排序在链表上有两种实现路线：

• 自顶向下（递归）：利用快慢指针找到链表中点，把链表切成两半，递归排序左右半段，再合并。时间O(n log n)，空间O(log n)，因为递归调用栈要压栈。
• 自底向上（迭代）：先把整个链表看成 n 个长度为 1 的有序子链表，然后两两合并成长度为 2 的有序子链表，再两两合并成长度为 4 的有序子链表，一直到整个链表有序。时间O(n log n)，空间O(1)。

两者时间复杂度相同，但空间复杂度不同。如果面试官没有明确要求空间，写自顶向下是最稳妥的，因为代码短、思路清晰、不易出错。但如果题目明确提出"只能使用O(1)额外空间"，或者面试官追问"能不能不用递归"，你就必须上自底向上。

我在实际刷题时，倾向先把自顶向下写出来，这能保证你在 15 分钟内拿到 AC。然后我会再用自底向上实现一遍，因为这是区分 "会做题" 和 "懂排序" 的重要分界线。

2.3 复杂度与稳定性分析

归并排序的时间复杂度是稳定的O(n log n)，不管数组本来有序还是完全逆序，都要切分和合并这么多次。对于链表而言，"切分"只涉及快慢指针的移动，"合并"只涉及比较两个头节点的大小后调整指针，所以实际运行速度在n较大时，明显优于插入排序和选择排序。

稳定性方面，归并排序是稳定排序，关键在于合并两个有序链表时，当两边值相等时优先取左边链表的节点。这个特性在面试中可以作为加分点提出来。比如问你：如果链表里有两个节点的val相等，排序后它们的相对顺序会变吗？你只要在合并时注意比较符号，写成if (left.val <= right.val)而不是<，就能保证稳定。

空间复杂度：迭代版额外空间是O(1)（只用了几个指针），递归版是O(log n)（栈空间）。严格来说，递归版不满足进阶要求，但 LeetCode 的测试用例对空间卡得并不严，能过。不过面试时最好主动说明这一点，展示自己的严谨。

3. 实操实现：两种写法的完整代码与细节

3.1 自顶向下归并排序（递归）

先用最经典的递归写法作为突破口。整体分三步：

1. 找到链表中点，把链表切成前后两半。
2. 对前后两半分别递归调用sortList。
3. 合并两个有序链表。

找中点用快慢指针：slow每次走一步，fast每次走两步，当fast到达末尾时，slow刚好在中点。这里有个很容易踩坑的细节：怎么保证前半段的最后一个节点的next指向null，从而真正断开链表？做法是当fast走两步之前，先记录一个prev指向slow的前一个节点，循环结束后把prev.next置为null。

代码（Java 版）：

class Solution { public ListNode sortList(ListNode head) { if (head == null || head.next == null) { return head; } ListNode prev = null; ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { prev = slow; slow = slow.next; fast = fast.next.next; } prev.next = null; ListNode left = sortList(head); ListNode right = sortList(slow); return merge(left, right); } private ListNode merge(ListNode left, ListNode right) { ListNode dummy = new ListNode(0); ListNode cur = dummy; while (left != null && right != null) { if (left.val <= right.val) { cur.next = left; left = left.next; } else { cur.next = right; right = right.next; } cur = cur.next; } cur.next = left != null ? left : right; return dummy.next; } }

注意看merge里面的dummy节点，这是个技巧。有些人在合并时习惯先取一个较小的头节点作为结果头，再逐步接，这样需要额外写 if 分支处理头节点，容易出错。用dummy节点可以统一逻辑，最后直接返回dummy.next。

3.2 自底向上归并排序（迭代）

迭代版的思路要反过来，从最小的有序块开始，逐步扩大。核心是控制步长len，初始为 1，每次翻倍，直到len >= n。

每一轮循环做的事情是：把原始链表按长度为len切成一段一段的，每两段一组，合并成一个长度为2*len的有序段，再接回结果链表的尾部。

关键代码（Python 版，便于演示指针操作）：

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 len_ = 1 while len_ < length: pre = dummy cur = dummy.next while cur: # 切出第一段 left = cur right = self._cut(left, len_) # 如果第二段为空，说明只剩一段，本轮循环结束 if not right: break cur = self._cut(right, len_) # 合并两段 pre.next = self._merge(left, right) while pre.next: pre = pre.next pre.next = cur len_ *= 2 return dummy.next def _cut(self, head, n): # 从 head 开始切掉 n 个节点，返回后半段的头（或 None） 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, l2): dummy = ListNode(0) cur = dummy while l1 and l2: if l1.val <= l2.val: cur.next = l1 l1 = l1.next else: cur.next = l2 l2 = l2.next cur = cur.next cur.next = l1 or l2 return dummy.next

_cut函数承担了"按指定长度切分链表"的任务，它会把前半段的最后一个节点的next置空，并返回后半段的头节点。这个函数写熟练了，其实比递归版的快慢指针更直观。

迭代版里最容易出错的地方是：在每一轮合并完之后，要把合并结果接到上一轮的尾部，并且用cur记录下一对段的起始位置。我在第一次写的时候，漏掉了pre.next = cur这行，结果最后的链表后半段直接丢了。调试了整整半小时才意识到，原来是把cur保存的剩余链表给覆盖了。

3.3 关键边界条件与指针操作

链表排序的边界条件其实就那么几个，但只要有一个处理不到位，程序就会挂：

• 空链表和单节点链表：直接返回head，无需排序。这是递归和迭代的公共退出条件。
• 偶数长度链表的中点：快慢指针找中点时，fast结束条件要写成while (fast != null && fast.next != null)。如果只写fast.next != null，奇数长度链表没问题，但偶数长度链表会访问空指针。
• 切分链表时：确保前半段的next断开，否则合并时会出现环。递归版的prev.next = null和迭代版的_cut中的head.next = None都是干这个事的。
• 合并时：一个链表为空时，直接把另一个链表剩余部分接上去，不需要一个个遍历。总有人在这里写一个while循环去拼单向指针，白白多出O(n)时间，而且容易额外创建节点。

下面这张表总结了两种写法的关键差异：

4. 变体与扩展：不只是排序链表

4.1 插入排序链表

LeetCode 第 147 题就是排序链表的"表弟"：使用插入排序对链表排序。它的时间复杂度是O(n^2)，不适合规模大的数据，但它是理解"指针重接"的好题。做法是维护一个已排序部分的链表，每次从未排序部分取一个节点，扫描已排序部分找到合适位置插入。

原理不复杂，但实现时要小心：因为链表只能单向移动，你没法像数组那样从后往前找插入点，只能每次都从已排序部分的头开始比较。这意味着最坏情况下，每个节点都要遍历完整个已排序部分，总时间O(n^2)。

这道题和排序链表对照着做非常有意思。你会发现：插入排序在链表上比在数组上更"碎"，因为要不断调整前驱节点的next指针；而归并排序在链表上却意外地干净。这能帮你加深印象——数据结构不是容器的外壳，算法选型必须适配结构特性。

4.2 链表快速排序的问题

评论区经常有人问：为什么不用快速排序？我在这里一次性说清楚。快速排序的核心是分区操作：选一个基准值，把数组分成小于基准和大于基准两半，然后递归排序两半。数组快排能通过左右下标同时向中间扫描来做分区；但单链表只能单向遍历，要模拟这个过程，常见策略是维护两个链表（小于基准和大于基准），遍历原链表把节点分别挂到两个链表后，再递归排序。这个思路的核心代码如下：

private ListNode quickSort(ListNode head) { if (head == null || head.next == null) return head; ListNode pivot = head; ListNode smallerDummy = new ListNode(0); ListNode largerDummy = new ListNode(0); ListNode smaller = smallerDummy, larger = largerDummy; ListNode cur = head.next; while (cur != null) { if (cur.val < pivot.val) { smaller.next = cur; smaller = smaller.next; } else { larger.next = cur; larger = larger.next; } cur = cur.next; } smaller.next = null; larger.next = null; ListNode sortedSmaller = quickSort(smallerDummy.next); ListNode sortedLarger = quickSort(largerDummy.next); ListNode pivotNode = pivot; pivotNode.next = sortedLarger; if (sortedSmaller == null) return pivotNode; ListNode tail = sortedSmaller; while (tail.next != null) tail = tail.next; tail.next = pivotNode; return sortedSmaller; }

看着也能写，但问题在于：最坏情况下，如果链表已经有序或者逆序，快排每次选的基准都是最大或最小，递归深度会退化到O(n)，总时间退化到O(n^2)。虽然归并排序也存在"拆半"的固定开销，但它每次都严格切一半，所以时间复杂度雷打不动是O(n log n)。这一点在面试里很重要：你不希望一个理论上限是O(n log n)的算法，在实际数据上跑出平方级的复杂度。

4.3 面试追问场景

面试官在排完序链表后，喜欢从这几个角度继续追问：

• "你能不用递归完成排序吗？" 这就是逼你写自底向上归并。
• "如果链表里存储的不是数字，而是自定义对象，怎么排序？" 答案很简单：给链表节点或对象实现比较器，合并时调用compareTo。归并排序的稳定性在这里就有价值了。
• "如果链表非常长，比如百万级节点，递归会怎样？" 理论上递归深度log n并不大，百万节点也就 20 层左右，但如果是退化链表会导致递归深度变大。实际场景中，面试官主要想听你说：迭代版没有递归栈空间，更适合大规模数据。
• "能不能在原地排序，不创建新节点？" 归并排序合并时只需要调整next指针，不需要创建new ListNode，这就是原地排序（稳定排序）的体现。

把这些追问准备充分了，排序链表这一题的"面试含金量"才算真正吸收完毕。

5. 常见问题与调试实录

5.1 递归栈溢出？

很多人担心递归版会不会栈溢出。我先给结论：在 LeetCode 测例下，几乎不会。原因很简单，归并排序的递归深度等于log2(n)，即使链表有10^5个节点，深度也就 17 层左右，完全在 Python 和 Java 默认栈允许范围内。但如果你面试时把链表规模说成"内存能放下就有多大"，那理论上深度也是对数级，只要链表是线性的，递归深度就不会超过ceil(log2(n)) + 1。

真正会导致栈溢出的场景是什么？是切分时没断干净，递归调用没有减少节点数量。比如快慢指针找中点时写错，导致left和right仍然共享节点，最终递归退化成线性结构，深度变成n，那才会爆栈。所以遇到栈溢出，先别急着怀疑递归，去检查你的切分逻辑。

5.2 指针悬空与环的形成

链表排序最常见的运行错误是"结果里出现环"，症状是程序在遍历结果时死循环。我实际调试时通常用一个小技巧：在测试代码里手动构造一个三到五个节点的链表，排序后挨个输出节点值，同时打印节点哈希或内存地址（Java 里可以用System.identityHashCode，Python 里可以用内置的id），如果某个节点的next指向了它自身，立刻就能发现。

环的形成原因，我总结了三个：

• 切分时没有断开链表。递归版的prev.next = null漏写，或者迭代版_cut里head.next = None没执行。
• 合并时dummy节点和原头节点混用。有人把dummy.next.head写反，导致返回的头节点还是旧的，合并过程中环就绕起来了。
• 用while (cur != null)遍历时，循环内把cur.next改掉，但没有保存cur.next的临时值。这是很多人在合并完最后一段时犯的错误。

5.3 性能对比与测试

为了直观感受两种写法的差异，我曾用本地环境生成过一组随机数链表进行测试，节点数分别为 1000、10000、100000，记录排序时间。结果很有意思：

（数据基于我自己的机器，不同语言和 JDK 版本会有波动，但整体趋势可参考。）

大样本下两者耗时几乎一致，因为核心操作都是切分和合并，差别主要在递归函数调用的开销。但迭代版代码更长，调试更费劲，所以如果只是刷题过测试，我推荐写递归版；如果是面试和同学聊复杂度时想展示实力，就补一份迭代版。

6. 经验总结与刷题建议

6.1 这题带给我的收获

排序链表是我在 LeetCode 上重复刷过三遍以上的题目。第一遍我用"值交换法"——把链表转成数组再排序——过了 AC，当时还觉得自己很聪明。后来看题解才发现，这种方法虽然能过，但在面试里完全不够看。第二遍我认真写了递归归并，终于理解了快慢指针在链表中点的妙用。第三遍我强迫自己不看题解实现迭代版，前前后后卡了不知道多少次，最后把_cut和pre.next = cur的衔接关系彻底搞明白。

我的体会是：链表排序题不像动态规划那样套路多，它更像是一系列基础操作的"组合拳"——找中点、断开、合并、接回。这些操作单独练，每道都是简单题；合在一起，就是中等题到难题的跨度。如果你能把排序链表做到 20 分钟内无 bug 写完，链表类的其他题目（反转链表、回文链表、重排链表）都会顺手很多。

6.2 相关题目推荐

刷完排序链表之后，我建议按这个顺序补几个兄弟题：

• LeetCode 21：合并两个有序链表（排序链表的核心子步骤）。先把这个刷到闭眼能写，再做排序链表就轻松一半。
• LeetCode 876：链表的中间节点（找中点方法练手）。排序链表里的快慢指针技巧，这一题会单独考。
• LeetCode 147：对链表进行插入排序（对比着做，理解O(n^2)和O(n log n)的差异）。
• LeetCode 143：重排链表（综合应用找中点、反转链表、合并链表，锻炼拆解复杂操作的能力）。

最后分享一个小技巧：我每次写链表排序前，都会习惯性画三个节点的图，标出排序前后每个节点的next指向哪里。画着画着你就会发现，链表排序本质上只是改变了有限几个指针的指向，一旦你脑子里有这个"指针地图"，写代码就不容易出错。这个习惯支撑我写过了很多链表题，希望对你也有用。