彻底搞懂排序链表：递归与迭代归并排序详解

直接进入正题。写过 LeetCode 148 的朋友应该都有印象：排序链表这道题，第一次看到我脑子里蹦出来的解法是“把链表拖进数组，sort 完再穿回去”——面试官一个眼神我就知道，这条路八成不是他想听的。链表这种东西，最大的特点就是不能随机访问，数组排序里玩得溜的快速排序、堆排序，一碰到链表经常抓瞎；插入排序虽然能写，但 O(n²) 在稍大的数据量下就是灾难。真正适合链表的排序方法是归并排序，原因很简单：合并两个有序链表只需要改指针，不需要额外搬数据，天然契合链表的“长相”。

这篇文章就围绕排序链表展开，重点讲两种最实用的归并排序实现：自顶向下的递归版，以及自底向上的迭代版。前者是面试中绝大多数人会写的方案，代码清晰好讲；后者空间复杂度能做到 O(1)，是追问时的加分项。两种方法我都会给出完整代码、运行过程拆解以及高频踩坑点，顺便聊聊为什么插入排序、快速排序在链表上不那么好使。适合正在刷链表题、准备面试，或者对复杂指针操作有点发怵的开发者参考。

1. 链表排序的整体思路：数组排序为什么在链表上“失灵”

1.1 经典排序算法在链表上的先天不足

先给刚接触链表的同学补个背景。数组排序能快速进行，核心优势是 O(1) 随机访问：想拿第 100 个元素，arr[99] 一下就到。链表的节点只知道自己和下一个节点，想拿第 100 个元素，只能从 head 开始一个一个 next 走过去，复杂度 O(n)。

这个差异直接淘汰了一批算法：

• 快速排序：快排的核心是 partition，需要从左右两端向中间扫描并交换元素。链表没有“往回走”的指针，双端扫描要么重写逻辑，要么频繁 O(n) 遍历，效率完全体现不出来。
• 堆排序：建堆需要按下标访问父节点和子节点，链表做不到随机下标访问。
• 插入排序：虽然单链表实现插入排序不算复杂，但每插入一个元素都可能从头遍历，整体是 O(n²)。LeetCode 147 专门让你写链表的插入排序，练手感不错，但实际用途有限。

剩下来的主流方案就是归并排序。归并排序的“分”需要找中点，链表虽然没法随机访问，但用快慢指针一次遍历就能找到中间节点；“合”的过程同样只需要调整 next 指针。可以说，归并排序是为链表量身定做的排序方法。

1.2 两种归并排序：先分后合与先合后分

归并排序有两种落地思路，本质是一样的，区别在“分”和“合”的顺序：

• 自顶向下（递归版）：把整条链表一分为二，各自递归排序，再合并两条有序链。思路清晰，是绝大多数教材和题解里的默认写法。
• 自底向上（迭代版）：先把链表看成 n 个长度为 1 的有序子链，相邻两两合并，得到长度为 2 的有序子链；再相邻合并，得到长度为 4 的有序子链；直到合并成一条完整的有序链表。

两种方法的时间复杂度都是 O(n log n)，空间上递归版需要 O(log n) 的调用栈空间，迭代版可以做到 O(1) 额外空间。后面我会分别拆解。

2. 方法一：自顶向下的归并排序（递归版）

2.1 三个子问题：找中点、合并两个有序链表、递归分解

自顶向下归并排序可以拆成三个函数层面的问题：

找中点并断开

链表不像数组能用下标直接二分，需要快慢指针。慢指针每次走一步，快指针每次走两步，快指针到末尾时，慢指针正好在中间。这里有一个细节：快指针需要从 head->next 出发，而不是 head 本身。原因很简单，当链表长度为偶数时，我们希望慢指针停在左半段的最后一个节点上，这样 mid 指向右半段的起点，直接把 slow->next 断掉，就能得到左右两条独立链表。

如果快指针也从 head 出发，长度为 2 的链表会让 slow 停在第二个节点，mid 变成 NULL，分割就错了。这个初始化差异是新手最容易写错的点之一。

合并两个有序链表

合并逻辑和“合并两个有序数组”一样，只是这里用指针拼接。使用哑节点（dummy node）可以避免处理“第一个节点谁当头部”的分支判断，统一从 dummy->next 开始返回。

c复制struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode dummy;
    dummy.next = NULL;
    struct ListNode* tail = &dummy;

    while (l1 && 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 ? l1 : l2;
    return dummy.next;
}

注意比较符号用 <=，这样相同值的节点会优先取前一个链表的节点，保证排序的稳定性。虽然链表排序对稳定性要求没那么敏感，但面试时能说出这个细节，通常是加分项。

递归分解

递归出口是：链表为空，或者只有一个节点。一个节点天然有序，不需要再拆。每次递归先找中点，把链表切成 left 和 right 两段，分别递归调用 sortList，最后合并。

2.2 完整代码实现

c复制struct ListNode* sortList(struct ListNode* head) {
    // 空链表或单节点，直接返回
    if (!head || !head->next) {
        return head;
    }

    // 快慢指针找中点，slow 最终停在左半段最后一个节点
    struct ListNode* slow = head;
    struct ListNode* fast = head->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    // 断开左右两段
    struct ListNode* mid = slow->next;
    slow->next = NULL;

    // 递归排序左右两段
    struct ListNode* left = sortList(head);
    struct ListNode* right = sortList(mid);

    // 合并两个有序链表
    return mergeTwoLists(left, right);
}

整个代码不长，核心逻辑就三件事：找中点、递归、合并。很多人在纸上画递归过程觉得很简单，真正手写的时候却容易在 slow 和 fast 的初始值上翻车。下面的运行过程拆解能帮你建立直观印象。

2.3 一次递归过程的完整拆解

以链表 4 -> 2 -> 1 -> 3 -> 5 为例，看看 sortList 是怎么工作的。

第一层调用：

• head 指向 4，链表长度 5。
• 快慢指针开始走。slow 初始在 4，fast 初始在 2。
• 第一轮：fast 在 2 且 fast->next 在 1，条件成立，slow 走到 2，fast 走到 1。
• 第二轮：fast 在 1 且 fast->next 在 3，条件成立，slow 走到 1，fast 走到 5。
• 第三轮：fast 在 5，但 fast->next 为 NULL，循环结束。
• 此时 slow 指向 1，mid 指向 3。把 1->next 置为 NULL，链表被切成 4 -> 2 -> 1 和 3 -> 5 两段。

接下来递归处理左半段 4 -> 2 -> 1：

• 快慢指针切分后得到 4 和 2 -> 1。
• 4 是单节点，直接返回。
• 2 -> 1 继续切分：slow 在 2，mid 在 1，切成 2 和 1，两个单节点各自返回。
• 合并 2 和 1，得到 1 -> 2。
• 再合并 4 和 1 -> 2，得到左半段结果 1 -> 2 -> 4。

右半段 3 -> 5 同理，切分成 3 和 5，合并得 3 -> 5。

最后第一层调用把 1 -> 2 -> 4 和 3 -> 5 合并：1 最小，接着 2 和 3 选 2，然后 3 和 4 选 3，然后是 4 和 5 选 4，最后接上 5。最终结果 1 -> 2 -> 3 -> 4 -> 5。

整个过程就是标准的“先拆到底，再逐层合”。理解递归版的关键是不要试图跟踪每一层递归的指针状态，只需要相信：sortList 能返回一条有序链表，mergeTwoLists 能把两条有序链表合成一条。这两个“相信”成立，整个算法就是对的。

2.4 递归版最容易踩的坑

坑一：忘记断开 slow->next

找到中点后，如果不把 slow->next 置为 NULL，左右两段仍然粘连在一起，递归进入死循环，最终栈溢出。这是最常见的错误。

坑二：快慢指针初始化错误

fast 必须从 head->next 出发。我之前说过，从 head 出发会让偶数长度的链表切分位置偏右一个节点，mid 可能为 NULL，直接导致递归没法正确处理。

坑三：merge 函数里修改了头节点但没有返回新头

合并后链表的头部可能不是原来的 head，而是 l2 的第一个节点。如果不返回 dummy.next，而是返回 head，结果链表会丢掉头部。写 merge 时一定要养成返回新头节点的习惯。

3. 方法二：自底向上的归并排序（迭代版）

3.1 整体思想：从长度为 1 的块开始玩拼接

自底向上归并排序的思路可以这样理解：先把链表里每个节点单独看作一个有序块，块长度为 1。然后相邻的块两两合并，得到一堆长度为 2 的有序块；再相邻合并，得到长度为 4 的有序块。每一轮块的长度翻倍，直到最后只有一个块，排序完成。

这个思路和递归版相反：递归版是“先拆到最小，再一层层合回去”，迭代版是“从最小开始，直接一层层合上去”。好处是不需要递归调用，空间复杂度 O(1)，数据量极大时不会爆栈。

实现上需要三个辅助能力：

• 遍历链表，数出总长度 length。
• 按给定长度切下一段子链，并返回剩余部分（split 函数）。
• 合并两条有序子链（merge 函数，和递归版完全相同）。

3.2 核心辅助函数 split 和 merge

split 函数是我比较推荐单独封装的一个工具，它负责把一个子链的前 n 个节点切出来，断掉尾部指针，返回后面剩余链表的头节点：

c复制struct ListNode* split(struct ListNode* head, int n) {
    // 从 head 开始向后走 n-1 步
    struct ListNode* p = head;
    while (--n && p) {
        p = p->next;
    }
    if (!p) {
        return NULL; // 子链不足 n 个节点，无需切割
    }
    struct ListNode* rest = p->next;
    p->next = NULL;  // 切断
    return rest;
}

有了 split 之后，自底向上的主循环就变得非常清晰：每次从当前指针 cur 出发，第一个 split 切出第一个子链 h1，第二个 split 从 h2 开头切出第二个子链，rest 保存剩余链表。把 h1 和 h2 合并后接到结果链表的尾部，然后继续处理 rest。

注意 split 返回 NULL 时的情况：说明剩下的节点不足一个完整的子链长度。这时不需要再做合并，直接把剩余子链接到结果尾部即可。

merge 函数直接复用上一节写过的 mergeTwoLists，这里不再重复贴。

3.3 完整代码实现

c复制struct ListNode* sortList(struct ListNode* head) {
    if (!head || !head->next) {
        return head;
    }

    // 1. 计算链表长度
    int length = 0;
    struct ListNode* p = head;
    while (p) {
        length++;
        p = p->next;
    }

    struct ListNode dummy;
    dummy.next = head;

    // 2. 每轮合并长度为 subLen 的相邻子链
    for (int subLen = 1; subLen < length; subLen <<= 1) {
        struct ListNode* pre = &dummy;
        struct ListNode* cur = dummy.next;

        while (cur) {
            // 切出第一个子链 h1，长度 subLen
            struct ListNode* h1 = cur;
            struct ListNode* h2 = split(h1, subLen);

            // 剩余不足一个子链，直接保留不动
            if (!h2) {
                pre->next = h1;
                break;
            }

            // 切出第二个子链，并拿到剩余部分
            struct ListNode* rest = split(h2, subLen);

            // 合并两个有序子链，接到结果尾部
            pre->next = merge(h1, h2);

            // pre 移动到合并后的尾部
            while (pre->next) {
                pre = pre->next;
            }

            // 继续处理剩余部分
            cur = rest;
        }
    }

    return dummy.next;
}

我建议你在本地跑这段代码时，在纸上模拟一遍 5 -> 4 -> 3 -> 2 -> 1 的过程：

• 第一轮 subLen = 1，切出一堆单节点块，两两合并成 4 -> 5、2 -> 3，最后一个节点 1 单独留下。
• 第二轮 subLen = 2，把 4 -> 5 和 2 -> 3 合并成 2 -> 3 -> 4 -> 5，最后接上 1。
• 第三轮 subLen = 4，合并 2 -> 3 -> 4 -> 5 和 1，得到 1 -> 2 -> 3 -> 4 -> 5。

这个过程的妙处在于：每一轮结束后，链表从头开始都是若干个长度为 subLen 的有序块，块数减半，下一轮继续两两合并，直到只剩一个块。

3.4 迭代版的易错点与边界处理

易错点一：merge 之后 pre 指向哪里

pre 是结果链表当前尾部的缩进指针。合并完 h1 和 h2 后，必须把 pre 移动到合并链表的最后一个节点。很多人直接写成 pre = pre->next，这只移动了一个节点，下一轮合并的结果会接在错误的位置。

易错点二：最后一个不足 subLen 的子链不能丢

while (cur) 循环里，如果 h2 为空，说明剩余节点少于 subLen，此时直接把 h1 接到 pre 后面，然后 break。这里不能什么都不做，否则剩余部分会丢失。

易错点三：每轮循环开始前 cur 要从 dummy.next 开始

每一轮 subLen 变化后，链表头部可能已经改变（合并后头部可能不是原来的 head），所以不能用原来的 head 作为本轮起点，必须从 dummy.next 开始重新遍历。

易错点四：subLen 用 int 可能溢出

链表长度在一般情况下不会太大，但用 subLen <<= 1 时要小心，如果 subLen 超过 INT_MAX 会变成负数。实际刷题场景很少遇到，但可以考虑用 subLen *= 2 防止移位符号问题。

4. 两种方法对比、选型与题目实战建议

4.1 递归版 vs 迭代版：一张表格看明白

我的建议很简单：优先把递归版写到滚瓜烂熟，因为它能快速解决 90% 的问题。迭代版也要能默写出来，因为面试官一旦追问“递归的空间复杂度能优化吗”，你能写出迭代版会是一个很亮眼的加分项。

4.2 LeetCode 148 的实战选型思路

LeetCode 148 对空间复杂度的要求是 O(1) 额外空间，严格来说递归版的空间复杂度 O(log n) 并不满足题目的字面要求。但在实际判题环境中，递归版通常也能通过，因为 O(log n) 的栈空间在普通数据规模下完全可以接受。

如果你在意题目的严格限制，直接交迭代版。我见过不少人在评论区纠结这个问题，我的看法是：不要因为空间复杂度不满足就不写递归版，而是要把两种都掌握。面试答递归版讲思路，面试官追问空间再补充迭代版，这才是最稳妥的策略。

另外，如果用 C++ 或 Java 写，代码结构基本一致，只是要注意：

• C++ 中指针/引用语义更复杂，merge 里如果用引用传递头节点，要格外小心悬空指针。
• Java 中对象引用本质就是指针，但不需要手动管理内存，写起来会轻松一点。
• Python 写链表排序要特别注意节点赋值和垃圾回收，不要边合并边断开导致节点被回收。

4.3 为什么插入排序在链表上仍然“有市场”

很多教材讲到链表排序时会提插入排序，LeetCode 147 也专门有一题。链表的插入排序确实比数组版简单：不需要大量搬移元素，只需要找到合适位置然后修改前后节点的 next 指针。

但它的时间复杂度终究是 O(n²)。链表本身无法随机访问，每一趟插入最坏情况都要从头遍历，n 个元素就是 O(n²) 次比较。这个复杂度在大数据量下很难看，所以插入排序只适合“链表已经基本有序”或者“数据量很小”的场景。

我个人用它来做练习的价值是：插入排序能帮你加深对“链表断链和重接”的理解，特别是“寻找插入位置”和“更新前驱节点”这两个操作，和归并排序中的指针维护是相通的。

5. 常见问题与排错速查手册（含实测经验）

5.1 高频问题与排查思路

问题一：递归版运行时栈溢出

典型原因：slow->next 没有置 NULL，左右链表没有真正断开，递归无法收敛。排查方法：在 sortList 入口打印 head 和 head->val，看有没有出现同样的头节点反复传入。一旦发现重复，基本就是断链没断干净。

问题二：排序结果断成几截

典型原因：merge 返回的链表没有正确接到 pre 后面。递归版中，问题多半出在 tail->next = l1 ? l1 : l2 之后没有更新 tail；迭代版中，问题多半出在 pre 没有移动到合并后的尾部。

问题三：迭代版结果少了最后一个节点

典型原因：if (!h2) { pre->next = h1; break; } 漏写。剩余不足子链长度的部分如果没有被接上，就会丢失整段节点。

问题四：快慢指针找中点不正确

典型原因：fast 初始化为 head，而不是 head->next。如果你发现长度为 4 的链表被切成 3 和 1，就是慢指针停偏了。记住：fast = head->next，这样 slow 才停在左半段的最后一个节点。

问题五：merge 中比较用的是 < 而不是 <=

结果：相同值的元素顺序可能被打乱，链表排序虽然不是稳定排序的典型应用场景，但使用 <= 能保持稳定性，习惯养成后处理复杂排序需求时不容易踩坑。

5.2 调试链表排序的实用技巧

我在调试链表排序题时，习惯写一个简单但极其有用的调试宏，能把一条链表的全部节点值按顺序打出来：

c复制void printList(struct ListNode* head) {
    while (head) {
        printf("%d ", head->val);
        head = head->next;
    }
    printf("\n");
}

在 sortList 入口、split 之后、merge 之后分别调用，配合断点看，能很直观地发现哪一步把链表切错了、哪一步合并结果不对。链表这种“靠指针串起来”的数据结构，调试的时候最怕的就是脑子里想指针、眼睛却只看节点值。打印整条链的连续性，比单步跟指针高效得多。

另一个建议是：先写好 merge，再写主逻辑。merge 是两种方法共用的基础模块，它正确了，后面出问题时至少能排除一半嫌疑。先用两个手工构造的有序链表（比如 1 -> 3 -> 5 和 2 -> 4）测 merge，确认输出是 1 -> 2 -> 3 -> 4 -> 5，再往上搭 sortList 的框架。

5.3 关于空间复杂度的两个常见追问

面试环节常有人在“空间复杂度 O(log n)”上追问：

• 递归栈算不算额外空间？算。递归调用本身占用的调用栈空间是算法空间复杂度的一部分，这一点要诚实承认。
• O(log n) 在链表长度为 10 万时有多大？log₂(100000) 大约是 17 层递归栈，完全可接受。但如果链表长度到百万、千万量级，递归调用栈带来的压力会变得明显，这时迭代版 O(1) 空间的价值就体现出来了。

另外，我实测过 LeetCode 上的长链表用例：递归版在 5 万节点以内几乎没有性能差异，迭代版因为每轮都要通过 split 重新遍历边界，常数会略大，但两者在大 O 层面都是 O(n log n)，实际运行时间都在几十毫秒级别。所以选型时不需要过度担心常数因子，代码可读性优先。

5.4 练习建议：从这几组测试用例开始

自己练习时，建议至少跑这几类用例：

• 空链表：NULL。
• 单节点：1。
• 逆序链表：5 -> 4 -> 3 -> 2 -> 1。
• 有序链表：1 -> 2 -> 3 -> 4 -> 5。
• 重复值链表：3 -> 1 -> 2 -> 3 -> 1。

我在测试重复值链表时就发现过一个小问题：如果 merge 里用了 < 而不是 <=，排序结果虽然在值上没问题，但如果你用指针地址去追踪相同值的节点，能发现它们的先后顺序被改变了。刷题阶段这个细节不太影响正确性，但养成稳定排序的编码习惯没坏处。

我个人刷链表排序这段内容时，最大的体会是：真正困难的不是记住归并排序的模板，而是搞清楚每一行代码在“切断指针”和“重接指针”之间扮演的角色。迭代版尤其如此。建议你拿到代码之后，不要急着背，先自己手动模拟一两轮循环，把 pre、cur、h1、h2、rest 五个指针在纸上标出来，跟着循环走一遍。走完一遍，很多疑惑会自动消失。这个习惯也适用于其他链表相关的题目，希望对你有用。