归并排序时间复杂度 O(nlogn) 解析：LeetCode 148 排序链表

归并排序时间复杂度 O(nlogn) 解析：LeetCode 148 排序链表

一、引言

在刷 LeetCode 148.排序链表时，很多同学会对归并排序的时间复杂度 O(nlogn) 感到困惑：为什么它一定能达到这个复杂度？分解和合并的过程具体是如何贡献这个复杂度的？本文将通过详细的图解和代码分析，揭开归并排序时间复杂度背后的数学原理。

二、问题背景：LeetCode 148.排序链表

题目要求对链表进行排序，进阶要求时间复杂度 O(nlogn) 且常数级空间复杂度。归并排序正是满足这一要求的经典解法。

示例：

• 输入：4 → 2 → 1 → 3
• 输出：1 → 2 → 3 → 4

三、归并排序的核心思想：分而治之

归并排序采用分治策略，将排序问题分解为三个步骤：

1. 分解：将原问题分解成若干个规模较小的子问题
2. 解决：递归地解决这些子问题
3. 合并：将子问题的解合并成原问题的解

其时间复杂度可以用递归公式表示：

T(n) = 2T(n/2) + O(n)

其中：

• 2T(n/2)：分解成两个规模为 n/2 的子问题所需时间
• O(n)：合并两个有序子序列所需时间

四、为什么是 O(nlogn)？从二叉树的角度理解

4.1 分解过程形成一棵"递归树"

以 8 个节点的链表为例：8 → 4 → 2 → 1 → 7 → 5 → 3 → 6

分解过程（递归地寻找中点）：

(此处省略图片链接)

关键观察：

• 树的高度 = log₂n（8 个节点需要 log₂8=3 层分解才能得到单个节点）
• 每层处理的节点总数始终为 n（只是被分成了更小的子链表）

4.2 合并过程自底向上构建有序链表

从最底层的单个节点开始，逐层合并：

第 4 层（合并后）：[8] [4] → [4,8] [2] [1] → [1,2] [7] [5] → [5,7] [3] [6] → [3,6]
第 3 层（合并后）：[1,2,4,8] [3,5,6,7]
第 2 层（合并后）：[1,2,3,4,5,6,7,8]

五、时间复杂度逐层剖析

5.1 分解阶段的工作量

在递归版本的代码中，分解阶段主要工作在 searchMid 函数：

public ListNode searchMid(ListNode head) {
    ListNode fast = head.next, slow = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow; // 返回中点
}

每层的工作量计算：

层数	子链表个数	每个子链表长度	每层总遍历次数
第 1 层	1	n	n/2
第 2 层	2	n/2	2 × (n/4) = n/2
第 3 层	4	n/4	4 × (n/8) = n/2
…	…	…	…
第 log n 层	n/2	2	(n/2) × 1 ≈ n/2

结论：分解阶段每层的工作量都是 O(n)，共有 log n 层，所以分解阶段总时间复杂度 = O(n) × O(log n) = O(n log n)

5.2 合并阶段的工作量

合并阶段的核心是 mergeList 函数：

public ListNode mergeList(ListNode head1, ListNode head2) {
    ListNode h = new ListNode();
    ListNode p = h;
    ListNode p1 = head1, p2 = head2;
    while (p1 != null && p2 != null) {
        if (p1.val <= p2.val) {
            p.next = p1;
            p1 = p1.next;
        } else {
            p.next = p2;
            p2 = p2.next;
        }
        p = p.next;
    }
    p.next = (p1 == null ? p2 : p1);
    return h.next;
}

每层的工作量计算：

层数	合并的对数	每对合并的比较次数	每层总操作次数
第 1 层（自底向上）	4 对（n/2 对）	每对最多 2 次	≤ 4×2 = 8 ≈ n
第 2 层	2 对（n/4 对）	每对最多 4 次	≤ 2×4 = 8 ≈ n
第 3 层	1 对（n/8 对）	每对最多 8 次	≤ 1×8 = 8 ≈ n

结论：合并阶段每层的工作量也都是 O(n)，共有 log n 层，所以合并阶段总时间复杂度 = O(n) × O(log n) = O(n log n)

5.3 总时间复杂度

总时间复杂度 = 分解阶段 + 合并阶段 = O(n log n) + O(n log n) = O(2n log n) = O(n log n) （常数因子忽略）

六、两种实现方式的复杂度对比

6.1 递归实现（自顶向下）

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode slow = searchMid(head); // O(n) 分解
        ListNode tmp = slow.next; 
        slow.next = null;
        ListNode left = sortList(head); // T(n/2)
        ListNode right = sortList(tmp); // T(n/2)
        return mergeList(left, right); // O(n) 合并
    }
}

• 空间复杂度：O(log n)（递归调用栈）

6.2 迭代实现（自底向上）

class Solution {
    public ListNode sortList(ListNode head) {
        // ... 计算链表长度 length
        for (int subLength = 1; subLength < length; subLength <<= 1) {
            // 每轮 subLength 翻倍，共 log n 轮
            ListNode cur = dummy.next;
            while (cur != null) {
                // 提取两个长度为 subLength 的子链表
                // 合并它们 O(n)
                // ...
            }
        }
    }
}

• 空间复杂度：O(1)（满足题目进阶要求）

七、与其他排序算法的对比

排序算法	最好情况	平均情况	最坏情况	空间复杂度	稳定性
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n) 或 O(log n)	稳定
快速排序	O(n log n)	O(n log n)	O(n²)	O(log n)	不稳定
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	不稳定
插入排序	O(n)	O(n²)	O(n²)	O(1)	稳定

归并排序的最大优势：无论输入数据如何，都能保证 O(n log n) 的时间复杂度。

八、常见疑问解答

Q1：为什么分解阶段也算时间复杂度？不是只算合并吗？

A：分解阶段虽然不涉及元素比较，但需要遍历链表寻找中点（searchMid 函数），这些遍历操作同样消耗时间，需要计入总时间复杂度。

Q2：为什么说是 O(n log n) 而不是 O(n)？

A：因为需要 log n 层操作，每层都要处理 n 个元素。以 8 个元素为例，需要 3 层，每层处理 8 个元素，总操作次数约为 24 次（n log n），而不是 8 次（n）。

Q3：递归实现的空间复杂度为什么是 O(log n)？

A：递归调用会使用系统栈，最深时递归 log n 层（因为每次规模减半），所以需要 O(log n) 的额外空间。

九、总结

归并排序 O(n log n) 的时间复杂度来源于其完美的分治结构：

1. log n 层：每次将问题规模减半，形成高度为 log n 的递归树
2. 每层 O(n)：无论是分解阶段的寻找中点，还是合并阶段的比较合并，每层都需要处理所有 n 个元素
3. 层数 × 每层工作量 = O(log n) × O(n) = O(n log n)

这种"层数 × 每层工作量"的分析方法，不仅适用于归并排序，也是理解其他分治算法（如快速排序、二分查找）复杂度的核心思维模型。

十、题解

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

/**
 * 归并排序递归法
 */
class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode slow = searchMid(head);
        ListNode tmp = slow.next; 
        slow.next = null;
        ListNode left = sortList(head);
        ListNode right = sortList(tmp);
        return mergeList(left, right).next;
    }

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

    public ListNode mergeList(ListNode head1, ListNode head2) {
        ListNode h = new ListNode();
        ListNode p = h;
        ListNode p1 = head1, p2 = head2;
        while (p1 != null && p2 != null) {
            if (p1.val <= p2.val) {
                p.next = p1;
                p1 = p1.next;
            } else {
                p.next = p2;
                p2 = p2.next;
            }
            p = p.next;
        }
        p.next = (p1 == null ? p2 : p1);
        return h;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

/**
 * 自底向上的方法
 */
class Solution {
    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(0, head);
        for (int subLength = 1; subLength < length; subLength <<= 1) {
            ListNode pre = dummy;
            ListNode cur = dummy.next;
            while (cur != null) {
                ListNode p1 = cur;
                for (int i = 1; i < subLength && cur != null && cur.next != null; i++) {
                    cur = cur.next;
                }
                ListNode p2 = cur.next; 
                cur.next = null; 
                cur = p2;
                for (int i = 1; i < subLength && cur != null && cur.next != null; i++) {
                    cur = cur.next;
                }
                ListNode next = null;
                if (cur != null) {
                    next = cur.next; 
                    cur.next = null;
                }
                ListNode mergeList = mergeTwoList(p1, p2);
                pre.next = mergeList;
                while (pre.next != null) {
                    pre = pre.next;
                }
                cur = next;
            }
        }
        return dummy.next;
    }

    public ListNode mergeTwoList(ListNode head1, ListNode head2) {
        ListNode h = new ListNode();
        ListNode p = h;
        ListNode p1 = head1, p2 = head2;
        while (p1 != null && p2 != null) {
            if (p1.val <= p2.val) {
                p.next = p1;
                p1 = p1.next;
            } else {
                p.next = p2;
                p2 = p2.next;
            }
            p = p.next;
        }
        p.next = (p1 == null ? p2 : p1);
        return h.next;
    }
}