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

五、时间复杂度逐层剖析

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; // 返回中点
}

每层的工作量计算：

结论：分解阶段每层的工作量都是 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;
}

每层的工作量计算：

结论：合并阶段每层的工作量也都是 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) {
        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 cur = dummy.next;
            while (cur != null) {
                // 提取两个长度为 subLength 的子链表
                // 合并它们 O(n)
                // ...
            }
        }
        return dummy.next;
    }
}

• 空间复杂度：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);
    }

    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.next;
    }
}

/**
 * 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;
    }
}