排序链表最优解：自顶向下与自底向上归并排序全解析

排序链表这道题，刷过 LeetCode 148 或者准备过大厂算法面试的朋友应该都不陌生。它把“排序”和“链表”这两个经典考点拧在一起，是我在技术面试时特别喜欢问的一道题：既能考察你对链表指针操作的熟练度，又能看出你递归和迭代两条腿是不是都站得稳，还能试探你对时间复杂度和空间复杂度的理解到底停在背结论还是真懂。

网上这道题的题解确实不少，但很多要么甩个代码就跑，要么只讲一种方法，看完还是不知道自己能不能手撕下来。这篇我打算把两种最主流的解法——自顶向下递归归并、自底向上迭代归并——从头到尾拆透，每一步为什么要这么写、边界条件为什么是那样、哪里最容易翻车，全部摊开讲。结尾再补一个插入排序的思路和快速排序为什么不适合链表的分析，让你面试时不管被问到哪个角度，心里都有底。

适合看这篇的人：正在刷 leetcode 准备面试的、复习数据结构期末考链表排序的、以及工作中真的遇到"给我一个链表把它排好序"这种需求的工程同学。不管你是刚入门还是已经会写，我相信里面都能翻出一两个值得注意的细节。

1. 排序链表到底是什么？为什么它比数组排序更讲究？

1.1 链表和数组在排序上的根本差异

我们平时最熟悉的排序套路，都是建立在数组的随机访问能力之上的。数组排好序后可以直接按下标取中间元素、可以原地交换、可以用快慢下标双向扫描，但链表这些统统做不到。

单链表是个什么结构？每个节点只知道自己后面是谁，不知道前面是谁，更不知道后面第几个是谁。你要想拿到第 n 个节点，只能从 head 开始一步一步往后走。这意味着：

• 数组里的"交换两个元素"，在链表里如果处理不好，会直接把链的顺序搞断；
• 数组里的"取中间元素"，在链表里必须靠遍历或者快慢指针才能做到；
• 数组里的"二分查找思想"，在链表里因为随机访问是 O(n) 的，直接失去意义。

所以在面对"排序链表"这道题时，你首先得放下数组排序的那套惯性思维。你需要的算法，最好是那种不依赖随机访问、只依赖"把两个有序序列合起来"的能力的算法。说到这个，你会想到什么？没错，归并排序。

1.2 为什么归并排序是链表排序的天选方案

归并排序的核心操作是"合并两个有序序列"，这个操作天然不依赖随机访问。无论你要合并的是数组还是链表，核心逻辑都是：谁小就取谁。放到链表上，你根本不需要开辟额外数组来存放合并结果，只需要把节点的 next 指针重新串一遍就行。

顺便说一下归并排序那套朴素的复杂度理论：时间复杂度稳定在 O(n log n)，空间复杂度取决于你的实现方式。数组版本需要 O(n) 的临时数组，但链表版本因为可以原地重接指针，理论上甚至能做到 O(1) 的额外空间。

为什么我这么强调"稳定"两个字？因为在实际的技术面试里，你给出的解法并不需要"最坏情况最优"，而是需要"最坏情况也可控"。链表不像数组，一个 O(n²) 的快排在随机数据下也许跑得很快，但链表上你连随机访问都做不到，快排的优势根本无从发挥。而归并排序在最坏、最好、平均三种情况下都是 O(n log n)，这个稳定性在链表场景里是极其稀缺的。

1.3 两条路线的整体规划

围绕归并排序，链表上有两种经典的实现路线：

第一种是大家最熟悉的自顶向下（递归）归并。先把链表用快慢指针一分为二，递归排好左右两半，然后合并。思路清晰，代码简短，面试时最容易讲明白。缺点是要用递归栈，空间复杂度是 O(log n)，当然这个 log n 对正常的链表长度来说完全不是问题。

第二种是自底向上（迭代）归并。不递归，直接先把链表里相邻的每 1 个节点当一组，两两合并；然后每 2 个节点一组，两两合并；再然后每 4 个节点一组……直到整条链表变成一个有序组。整个过程只需要几个指针变量，真正做到了 O(1) 额外空间，工程上更扎实。

这篇文章的正文部分，我会把这两种方法从思路到代码到执行过程全部拆开讲。排序链表不是那种"看一眼就会"的题，它需要你自己在纸上走几遍指针变化才能真正吃透。所以请务必跟着后面的模拟过程一起过一遍，而不是光把代码复制下来就跑。

2. 动手前的三个基本功：找中点、合并、断链

在写归并排序之前，有三个操作你必须先滚瓜烂熟，否则后面代码写得再漂亮，运行起来也是一堆空指针。这三个基本功是：找链表的中点、合并两个有序链表、以及把链表从中间干净地切开。

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

找链表中点这件事，绝大多数人都知道用快慢指针：快指针一次走两步，慢指针一次走一步，快指针走到头时，慢指针就在中点了。但这里有一个极其容易翻车的细节：快指针要从 head.next 开始走，而不是从 head 开始走。

先说不这样做会怎样。假设链表只有两个节点 1 -> 2，快慢指针都从 head（节点1）出发。快指针一次走两步，第二次循环时 fast 会直接走到 null，此时慢指针只走到节点2，slow.next 就是 null。看起来好像没事？不对——你把 slow.next 置为 null 时，切出来的是节点1这个单独的节点，节点2呢？节点2由 fast 在最后一次跳跃中经过但没有被保留。真正的问题发生在链表中点为偶数个节点时，快指针从 head 出发会让慢指针偏到右半边的第一个节点，导致左右两边节点数量差超过 1，递归的时候容易出现子链表为空或递归不下去的情况。

而从 head.next 出发就巧妙地避开了这个问题。以 1 -> 2 -> 3 -> 4 -> null 为例，初始时 slow 在 1，fast 在 2。第一次循环：slow 走到 2，fast 走到 4；第二次循环 fast.next 为 null，退出。此时 slow 在 2，slow.next 就是 3，也就是中点。切出来左边是 1 -> 2，右边是 3 -> 4，干干净净。

再验证一下奇数个节点的情况：1 -> 2 -> 3 -> null，初始 slow 在1，fast 在2。第一次循环：slow 走到2，fast 走到 null（因为 next 两步越界）。退出时 slow 在2，中点右侧是 3，左边是 1 -> 2，同样切分正确。

所以这个细节请你死记硬背地记下来：找中点时，fast 初始化为 head.next 而不是 head。这不是玄学，是无数人踩过坑之后总结出来的最佳初始值。

2.2 合并两个有序链表：哨兵节点大法

归并排序的第二步——把两个已经有序的子链表合成一个更大的有序链表，这个操作本身就是一道很经典的题（LeetCode 21）。但我要在这里强调的不是"怎么合并"，而是"用什么姿势写才不容易错"。

最稳妥的写法是创建一个哨兵节点（dummy node），让一个尾指针 tail 始终指向已合并链表的最后一个节点。然后开始一个 while 循环，只要两个链表都没到尽头，就比较当前节点值的大小，谁小就把谁接到 tail.next 上，然后把对应的链表指针往后挪一格，tail 也跟着往后挪一格。

循环结束后，两个链表里必然还剩一个非空（除非两个都刚好消耗完），直接把 tail.next 指向那个剩下的链表头部即可。这一步是链表合并比数组合并效率高的核心所在：数组归并还得把剩余元素一个一个拷进临时数组，链表只需改一次 next 指针。

为什么哨兵节点这么重要？因为你在合并时根本不知道结果链表的头节点会是 l1 的头还是 l2 的头。与其写一堆 if 判断来初始化头节点，不如直接放一个占位的哨兵，最后返回 dummy.next。这是链表操作里最典型的"用一个假节点省掉一堆边界判断"的套路，后面的归并代码里你还会看到它。

2.3 把断链当成切豆腐：一次切一块

第三个基本功是"断链"——也就是把 mid 之前的那个节点的 next 指向 null。很多人写归并排序时容易忽略这一步，以为只要拿到中点前后两段链表就能递归了。但你要知道，链表这东西没有"段"的概念，如果不把左半部分的尾部切断，递归排左半部分时，它会沿着 next 指针一路遍历到右半部分去，整个分治结构彻底崩塌。

断链这个操作在代码上只是一句 slow.next = null 或者 curr.next = null，但它的意义非常重大。你可以把链表想象成一根长香肠，分治归并的第一步，就是拿刀在中间切一刀，分成两截；递归下去，每截再各自切成两截。每一刀切完，左右两边都是独立的新链表，谁都不欠谁的 next 指针。

这也就是为什么我在标题里说"最详细"——很多题解里这一刀切得极其随意，读者根本没有意识到这刀不切会出什么事。后面自底向上那套代码里，断链会更加频繁，一次要断很多处，如果理解不了"断开即独立"这个思维模型，迭代写法很容易写成一团浆糊。

3. 方法一：自顶向下归并排序（递归实现）

3.1 整体思路：分治三步走

自顶向下归并排序的思路，其实就是老祖宗传下来的分治三步走：

第一步 分解：用快慢指针找到链表中点，然后把链表从中间断开，形成左右两条子链表。
第二步 解决：递归地对左右两条子链表分别调用 sortList，直到子链表只剩空节点或一个节点（天然有序）。
第三步 合并：把排好序的左右两条子链表合并成一条有序链表返回。

这个思路翻译成人话就是：我现在不知道怎么把一整条乱序链表排好，但我很确定怎么把两条有序链表合成一条。那好，我就把大链表切到足够小，小到只有一两个节点时，它天然有序，然后一层层往回合并，每次合成都让链表更大、更有序，直到恢复成整条链表为止。

事实上这个策略在工程里也很常见——把一个复杂的任务递归拆成"小到不能再拆"的子任务，等子任务都有答案了，再逐层汇总。归并排序是这种思想最直观的代表。

3.2 完整实现与逐行注释

下面是自顶向下归并排序的 Java 实现，我先把代码整体贴出来，再去逐段解释。这里假设你已经定义好了题目默认的 ListNode 类：包含 val 字段和 next 字段。

java复制class Solution {
    public ListNode sortList(ListNode head) {
        // 递归终止条件：空链表或只有一个节点，天然有序
        if (head == null || head.next == null) {
            return head;
        }

        // 第一步：找中点，并把链表从中点处断开
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode mid = slow.next; // 右半部分头节点
        slow.next = null;         // 切断左半部分与右半部分的联系

        // 第二步：递归排序左半部分和右半部分
        ListNode left = sortList(head);
        ListNode right = sortList(mid);

        // 第三步：合并两个有序链表
        return merge(left, right);
    }

    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0); // 哨兵节点
        ListNode tail = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                tail.next = l1;
                l1 = l1.next;
            } else {
                tail.next = l2;
                l2 = l2.next;
            }
            tail = tail.next;
        }
        tail.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }
}

一共也就二十几行，但里面每一步都经不起粗心。我下面把容易出问题的几个点单独拎出来说。

第一，快慢指针的初始化。fast = head.next 这个细节我在 2.1 里已经详细解释过，这里不再重复。你要知道的是，它在这里直接关系到递归能不能收敛：如果 fast 也从 head 出发，2 个节点的链表会切出 1 个节点和 2 个节点的子链表，右边那条递归时会无限调用自己，最终爆栈。

第二，找完中点后的断链。slow.next = null 这句话不能少。少了它，虽然 mid 变量已经拿到了右半部分的头节点，但左半部分沿着 next 走到底时会走到右半部分去，sortList 处理的头尾范围就乱了。你可以自己试着把这一行注释掉跑一次，大概率会死循环，因为切分永远不干净。

第三，递归终止条件。head == null 这个条件看起来多余，其实非常重要。当链表只有两个节点 1 -> 2 时，中点切分后左半部分是节点1，右半部分是节点2，这些都还好。但如果是空链表输入呢？或者是某些极端情况切出来的子链表本身为空呢？没有 head == null 这行，sortList(null) 会直接空指针。所以别嫌它多余。

3.3 用一组输入模拟执行过程

我们拿一个具体的例子走一遍：5 -> 2 -> 3 -> 1 -> 4 -> null。

第一层递归，链表长度 5。快慢指针找中点：slow 走到 3，mid 是 1，断链后左链表是 5 -> 2 -> 3 -> null，右链表是 1 -> 4 -> null。

先递归处理左半部分 5 -> 2 -> 3。长度 3，快慢指针找中点：slow 走到 2，mid 是 3，断开后左链表是 5 -> 2 -> null，右链表是 3 -> null。

继续递归，左半部分 5 -> 2，长度 2：中点切分为 5 和 2，递归各自返回后 merge(5, 2) 得到 2 -> 5 -> null。右半部分 3 本来就一个节点直接返回。回到这一层 merge(2 -> 5, 3)，得到 2 -> 3 -> 5 -> null。左半部分搞定。

再看右边的 1 -> 4，长度 2：切分为 1 和 4，递归后 merge(1, 4) 得到 1 -> 4 -> null。

最后回到最外层，merge(2 -> 3 -> 5, 1 -> 4)，过程是：比较 2 和 1，取 1；比较 2 和 4，取 2；比较 3 和 4，取 3；比较 5 和 4，取 4；最后剩 5 直接接上。最终得到 1 -> 2 -> 3 -> 4 -> 5。整个过程没有任何数组参与，完全是指针在重新指来指去。

我建议你至少自己手动模拟一遍这个过程，因为你在纸上走指针的次数越多，后面写自底向上版本时就越明白每一轮到底在做什么。

3.4 复杂度分析与隐藏风险

自顶向下归并排序的时间复杂度是 O(n log n)，这个没问题。每一层递归都要遍历一遍全部节点来做划分和合并，一共有 log n 层，所以总共 O(n log n)。

空间复杂度这里我要说得严谨一点。递归实现虽然不需要额外数组，但递归调用本身会占用系统栈空间。每次调用栈上要保存参数、返回地址等信息，调用深度是 log n 层（因为每次切一半），所以额外空间是 O(log n)。对于 n = 10^5 的链表，log2(10^5) 大约是 17，完全没有任何栈溢出风险。哪怕 n 到 10^7，递归深度也才 24 层左右，同样不用担心。

那到底有没有"隐藏风险"？有一个：如果你在面试时把"归并排序空间复杂度"想当然地说成 O(n)，那就尴尬了。很多人从数组归并那里带过来的惯性思维会认为归并排序一定需要 O(n) 额外空间，但在链表这里，合并是原地重接指针，不需要额外数组，递归栈也只有 O(log n)。这一点是你面试时能加分的差异点，记得主动提。

4. 方法二：自底向上归并排序（迭代实现）

4.1 整体思路：从长度为 1 的块开始两两合并

递归版本好用是好用，但如果你被问到"能不能把空间优化到 O(1)"，就得拿出自底向上的迭代版本了。这个版本不用递归，不占系统栈，思路是：

先把链表里每一个单独的节点看作一个长度为 1 的有序块。
第一轮，把相邻的两个长度为 1 的块两两合并，得到若干个长度为 2 的有序块。
第二轮，把相邻的两个长度为 2 的块两两合并，得到若干个长度为 4 的有序块。
如此反复，直到整个链表成为一个有序块，排序结束。

整个过程非常像体育比赛里的淘汰赛晋级：先是两两对决，胜者晋级；然后是四人小组循环，再晋级；一层层上去，最后决出总冠军。唯一的区别是这里每次以两倍规模合并且最终只有"晋级"没有"淘汰"——所有节点都在经受排序。

这个思路的实现难度比递归版本高不少，因为它要求你能够在一次遍历中精准地切出两个长度为 subLength 的子链表，合并完再接回去，然后继续切下一组。你需要同时维护好几个指针，任何一个不小心，链表就串了。

4.2 完整实现与逐行注释

先看完整代码，我尽量让每一处的意图都清楚。

java复制class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        // 先统计链表总长度
        int length = 0;
        ListNode p = head;
        while (p != null) {
            length++;
            p = p.next;
        }

        ListNode dummy = new ListNode(0, head); // 哨兵，指向当前链表头
        
        // subLength 从 1 开始，每次翻倍，直到超过链表总长度
        for (int subLength = 1; subLength < length; subLength <<= 1) {
            ListNode prev = dummy;  // prev 指向已合并部分的尾部
            ListNode curr = dummy.next; // curr 指向待处理的第一个节点

            while (curr != null) {
                // 切出第一个长度为 subLength 的子链表
                ListNode head1 = curr;
                for (int i = 1; i < subLength && curr.next != null; i++) {
                    curr = curr.next;
                }

                // head2 是第二个子链表的头
                ListNode head2 = curr.next;
                // 切断第一个子链表的尾部
                curr.next = null;

                // 如果 head2 为空，说明没有第二个子链表了
                // 剩余的 head1 本身已有序，直接接上即可
                if (head2 == null) {
                    prev.next = head1;
                    break;
                }

                // 从 head2 开始，切出第二个长度为 subLength 的子链表
                curr = head2;
                for (int i = 1; i < subLength && curr.next != null; i++) {
                    curr = curr.next;
                }

                // 记录下一组的起点，并切断第二个子链表
                ListNode nextGroup = curr.next;
                curr.next = null;

                // 合并两个子链表，接在 prev 后面
                prev.next = merge(head1, head2);

                // prev 移动到已合并链表的尾部
                while (prev.next != null) {
                    prev = prev.next;
                }

                // 继续处理下一组
                curr = nextGroup;
            }
        }

        return dummy.next;
    }

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

我在这里额外说明一下 ListNode 的两个构造参数问题。leetcode 的 ListNode 定义通常是 ListNode(int val) 和 ListNode(int val, ListNode next) 两个构造方法，所以上面的 new ListNode(0, head) 应该可以直接编译。如果你本地用的是只有单参构造的版本，写 new ListNode(0) 然后手动 dummy.next = head 也是一样的。不要因为这种小差异卡住。

这个迭代版本最考验人的地方在于：每一轮外层循环结束之后，链表已经不再是原来的节点顺序了，而是变成了若干个有序块拼接在一起。下一轮开始时不取决于上一轮的块长度，而是统一按新的 subLength 重新切块。所以 curr = dummy.next 每次都从头开始处理，非常关键。

4.3 模拟执行关键过程

我们还是用 5 -> 2 -> 3 -> 1 -> 4 -> null 来走一轮。链表长度 length = 5。

subLength = 1 这一轮：

第一次进入 while，curr 指向 5。head1 = 5，切长度为 1 不用走步，head2 = curr.next = 2，然后切断 5 的 next，于是 5 单独成块。从 head2 = 2 开始，切长度 1，nextGroup = 3，切断 2 的 next。合并 head1=5 和 head2=2，结果是 2 -> 5。prev 接到 2，移动到 5，curr 指向 nextGroup=3。

第二次进入 while，curr 指向 3。head1 = 3，head2 = 1，合并后得到 1 -> 3。prev 接到 1，移动到 3，curr = nextGroup = 4。

第三次进入 while，curr 指向 4。head1 = 4，走一步找 head2，发现 curr.next 是 null，所以 head2 = null。此时没有第二个子链表了，直接把 4 接到 prev 后面，break。本轮结束后链表变成：2 -> 5 -> 1 -> 3 -> 4 -> null。

subLength = 2 这一轮：

链表现在是 2 -> 5 -> 1 -> 3 -> 4 -> null。subLength = 2，即每两个节点一块。

第一次 while，head1 = 2，走一步到 5，head2 = 5.next = 1，切断 5 的 next。从 head2=1 开始，走一步到 3，nextGroup = 3.next = 4，切断 3 的 next。合并 2 -> 5 和 1 -> 3，得到 1 -> 2 -> 3 -> 5。prev 接到 1，移动到 5。

第二次 while，curr = 4。head1 = 4，走一步发现 next 为 null，head2 = null，直接把 4 接到 prev 后面，break。本轮结束后链表变成：1 -> 2 -> 3 -> 5 -> 4 -> null。

subLength = 4 这一轮：

链表是 1 -> 2 -> 3 -> 5 -> 4 -> null。subLength = 4，此时只剩一组：head1 = 1，走三步到 5，head2 = 5.next = 4，切断 5 的 next。从 head2=4 开始，走一步发现没有了，nextGroup = null，切断 4 的 next（本来也是 null）。合并 1 -> 2 -> 3 -> 5 和 4，得到 1 -> 2 -> 3 -> 4 -> 5。prev 接到 1，移动到 5，curr = null，内层结束。

subLength = 8 时，8 < length = 5 不成立，外层循环结束。返回 dummy.next，排序完成。

整个过程中你会发现，最后一轮 4 -> 4 并不对称：左边 4 个节点，右边 1 个节点。但这完全不影响正确性，因为 subLength 只是"最大长度"，当剩余节点不足时，直接把不足长度的有序快接上就行，反正它内部已经有序。

4.4 为什么说这才是工程上更优的方案

自底向上归并排序在空间上做到了真正的 O(1)，只用了几个指针变量，没有递归栈，没有辅助数组。对于超长链表（比如百万千万级节点），递归版本虽然理论上 log n 也不高，但在实际工程环境里，每一次递归调用都有栈帧分配的开销，而迭代版本就是纯粹的循环加指针操作，编译器优化起来也更友好。

另外，自底向上的写法还有一个隐性价值：它是把链表排序和"外部排序"思想打通的关键。外部排序处理超大文件时，就是先把数据切分成若干可载入内存的块，块内排好序，再不断做多路归并。链表自底向上归并的每一轮，本质上就是一次"局部归并 + 整体重排"，理解了它，你对归并排序本身的理解会上一个新台阶。

不过实话说，面试时如果你能先把递归版本讲清楚，再自然地说出"我还可以用迭代把空间压到 O(1)"，就已经很漂亮了。两个版本不是竞争关系，而是递进关系。

5. 两个方案怎么选？常见问题与排坑实录

5.1 两种方法的直观对比

把两种方法放在一起看，最直接的差异体现在这几个维度上：

从这张表里能看出一个规律：如果你追求"面试现场写出的代码最不容易出错"，选递归版本；如果你追求"从工程角度无懈可击"，选迭代版本。我个人的面试策略是，先把递归版本写出来跑通，然后用几句话补充：这个版本空间复杂度是 O(log n)，如果面试官想要 O(1)，我还能改成自底向上的迭代写法。大多数面试官听到这句话就已经很满意了。

5.2 补充：插入排序法及其适用场景

除了归并排序，链表排序还有一条老路——直接插入排序，LeetCode 147 专门考这个。思路非常简单：维护一个已排序链表的头节点 dummy，然后遍历原链表，每拿到一个节点，就在已排序链表中找到合适的位置插入。

java复制public ListNode insertionSortList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode dummy = new ListNode(0);
    ListNode curr = head;

    while (curr != null) {
        ListNode next = curr.next;      // 先记住下一个节点
        ListNode pos = dummy;           // 从哨兵开始寻找插入位置

        // 找到第一个比 curr.val 大的节点前的位置
        while (pos.next != null && pos.next.val < curr.val) {
            pos = pos.next;
        }

        curr.next = pos.next;           // 插入到 pos 之后
        pos.next = curr;

        curr = next;                    // 继续处理下一个节点
    }
    return dummy.next;
}

这个算法的时间复杂度是 O(n²)，空间 O(1)，在数据量小时跑起来甚至可能比归并快，因为常数小。但它有一个非常适合的应用场景：当链表已经基本有序时，插入排序几乎可以退化成 O(n) 级别的操作——每次找插入位置时，pos 很快就会找到目标位置。所以在实际工程里，如果遇到"数据基本有序、量不大"的链表排序需求，插入排序完全有理由被优先考虑。我在面试里提到它，主要想展示自己对"不同场景选不同算法"的理解。

5.3 为什么不推荐用快速排序排链表

这个问题很多面试官爱追问。你如果投简历的岗位跟基础架构有关，几乎一定会被问到"能不能用快排排链表"。答案是可以，但不推荐，原因主要有三。

第一，快速排序的核心优势是"原地partition + 随机访问"，这两点在链表上都不成立。链表没有随机访问，partition 时要反复从头部往后找小元素、从尾部往前找大元素，单向链表连"从尾部往前"都做不到，只能换成单向扫描，效率大打折扣。

第二，快排的性能受基准值选择影响极大，最坏情况 O(n²)。在数组上，我们可以 O(1) 随机取一个基准值来规避；但链表上取中间值要遍历，取随机值更是麻烦，所以基准值选择基本等同于取头节点或尾节点，非常容易退化。

第三，即便你硬写出一个能跑的链表快排，它也是个不稳定的排序，而归并排序是稳定的。工程上一个稳定排序的价值很高，尤其是当数据需要多关键字排序时，稳定性能保证前面排序的相对顺序不被破坏。

所以结论很简单：链表排序的默认答案就是归并排序，快排就让它安安静静待在它的数组主场里就好。

5.4 高频问题速查表

我把实操中最常踩的坑和面试官最常问的问题整理成一个速查表，你在写完代码后可以对照自查一遍。

还有一个实操经验：写完代码后，一定要跑这几个边界测试用例：空链表、单节点链表、两个节点逆序链表、全部相同值的链表、以及一长串交替升降序的链表。尤其是"全部相同值"这个用例，如果你 merge 里用了 > 而不是 >=，虽然结果依然有序，但会破坏稳定性，在某些严格要求稳定排序的场景里就不符合要求了。

最后再分享一个我个人刷题时的小技巧。递归版本的 sortList 和迭代版本都依赖 merge 函数，而这个 merge 函数本身就是一类独立的考点。我建议你先把 merge 单独练到手感完全形成，再去练习 sortList 的两种写法。很多时候你不是不会排序链表，而是"合并两个有序链表"这个底层操作不够熟练，导致上层写起来心里发虚。先把地基打牢，上面的楼怎么盖都稳。

排序链表这道题，我前前后后给不下二十个候选人讲过。有人一开始只会用数组转回去排序，有人递归版本写得很顺但一提 O(1) 空间就卡住，也有极少数人能直接流畅写出自底向上的迭代版本。这道题的价值不在于"背下来一个答案"，而在于它逼着你把链表指针操作、递归与迭代、稳定排序、复杂度分析这几块能力同时调动起来。你把这几种方法都走一遍之后，再回头看链表相关的其他题目，会有一种"手里有粮，心里不慌"的感觉。