从分治合并到链表排序：探索链表排序的优雅解法

从现实场景说起

想象你是一个图书管理员，面前有一排待整理的图书。这些书连成一条长龙，每本书都链接着下一本书的位置信息。如何高效地将这些书按顺序排列？一个聪明的方法是将书架分成几个小区域，分别整理后再合并 —— 这就是归并排序的思想，也是我们今天要探讨的排序链表问题的核心。

问题的本质

LeetCode第148题"排序链表"要求我们对链表进行排序，要求时间复杂度为O(n log n)，空间复杂度为O(1)。这个要求让我们不能使用转换为数组等简单方法，而必须在链表结构上直接操作。

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

输入：-1 → 5 → 3 → 4 → 0
输出：-1 → 0 → 3 → 4 → 5

思路解析：自顶向下的归并排序

就像整理图书一样，我们可以采用"分而治之"的策略：

1. 分解：将书架分成大小相近的两半
2. 递归：分别整理两半的书
3. 合并：将两组整理好的书按顺序合并

这种方法的优雅之处在于：我们不需要关心子问题是如何被解决的，只需要专注于如何将两个有序的部分合并起来。

找中点的艺术

在实现分解步骤时，我们需要一个找中点的巧妙方法 —— 快慢指针。想象两个图书管理员：

• 一个每次移动两个位置（快指针）
• 一个每次移动一个位置（慢指针） 当快指针到达终点时，慢指针正好在中间位置。

分治排序的实现

public ListNode sortList(ListNode head) {
    // 基本情况：空链表或只有一个节点
    if (head == null || head.next == null) {
        return head;
    }
    
    // 1. 使用快慢指针找到中点
    ListNode slow = head;
    ListNode fast = head.next;  // 注意这里的初始位置
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    // 2. 断开链表，得到两个子链表
    ListNode secondHalf = slow.next;
    slow.next = null;  // 断开连接
    
    // 3. 递归排序两个子链表
    ListNode left = sortList(head);
    ListNode right = sortList(secondHalf);
    
    // 4. 合并两个有序链表
    return mergeTwoLists(left, right);
}

// 合并两个有序链表的辅助函数
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;
    
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            curr.next = l1;
            l1 = l1.next;
        } else {
            curr.next = l2;
            l2 = l2.next;
        }
        curr = curr.next;
    }
    
    // 处理剩余节点
    curr.next = (l1 != null) ? l1 : l2;
    
    return dummy.next;
}

空间优化：自底向上的归并排序

虽然上面的解法已经很优雅，但它使用了递归，空间复杂度为O(log n)。如果要严格满足O(1)空间复杂度的要求，我们需要改用自底向上的方法。

这就像图书整理时采用的另一种策略：

1. 先两本两本地排序
2. 再四本四本地合并
3. 然后八本八本地合并
4. 直到整个书架都排好序

迭代归并排序实现

public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    
    // 1. 计算链表长度
    int length = 0;
    ListNode curr = head;
    while (curr != null) {
        length++;
        curr = curr.next;
    }
    
    // 2. 创建虚拟头节点
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    
    // 3. 自底向上归并
    // step表示每次归并的子链表长度：1,2,4,8,...
    for (int step = 1; step < length; step *= 2) {
        ListNode prev = dummy;
        curr = dummy.next;
        
        while (curr != null) {
            // 3.1 分割第一个子链表
            ListNode left = curr;
            ListNode right = split(left, step);
            curr = split(right, step);
            
            // 3.2 合并这两个子链表
            prev = merge(left, right, prev);
        }
    }
    
    return dummy.next;
}

// 分割函数：向前数n个节点，返回下一个节点，并断开连接
private ListNode split(ListNode head, int n) {
    while (--n > 0 && head != null) {
        head = head.next;
    }
    
    ListNode rest = (head != null) ? head.next : null;
    if (head != null) head.next = null;
    return rest;
}

// 合并函数：合并两个有序链表，返回合并后的尾节点
private ListNode merge(ListNode l1, ListNode l2, ListNode prev) {
    ListNode curr = prev;
    
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            curr.next = l1;
            l1 = l1.next;
        } else {
            curr.next = l2;
            l2 = l2.next;
        }
        curr = curr.next;
    }
    
    curr.next = (l1 != null) ? l1 : l2;
    // 找到最后一个节点
    while (curr.next != null) {
        curr = curr.next;
    }
    
    return curr;
}

复杂度分析与比较

自顶向下的归并排序：

• 时间复杂度：O(n log n)
• 空间复杂度：O(log n)，递归调用栈
• 优点：代码简洁，思路清晰
• 缺点：不满足O(1)空间复杂度要求

自底向上的归并排序：

• 时间复杂度：O(n log n)
• 空间复杂度：O(1)
• 优点：符合题目空间要求
• 缺点：实现较复杂，不够直观

技巧总结

1. 快慢指针找中点的技巧
2. 分治思想的应用
3. 断开链表时的细节处理
4. 合并有序链表的技巧

实际应用延伸

链表排序的思想可以应用于：

• 大文件排序
• 分布式系统的数据排序
• 外部排序
• 流式数据处理

小结

排序链表的问题教会我们：

1. 如何将经典排序算法应用到特定数据结构
2. 空间优化的重要性和方法
3. 处理链表时的常用技巧
4. 分治思想在实际问题中的运用

这道题的启示：

• 经典算法可以根据具体场景灵活调整
• 空间复杂度的优化往往需要另辟蹊径
• 链表操作中的指针处理需要特别小心

记住：解决复杂问题如同整理一个大书架，关键在于找到合适的分解方式和合并策略！

---

作者：忍者算法 公众号：忍者算法

我准备了一份刷题清单，以及这些题目的详细题解，覆盖了绝大部分常见面试题。我可以很负责任地说，只要你把这些题真正掌握了，80%的算法面试都能遇到相似题目。公众号回复【刷题清单】获取～