148. 排序链表#

从现实场景说起#

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

问题描述#

题目目标#

给你链表的头结点 head ，请将其按升序排列并返回排序后的链表。进阶要求时间复杂度为 O(n log n)，且尽量使用常数级空间复杂度。

示例 1#

输入： head = 4 → 2 → 1 → 3 输出： 1 → 2 → 3 → 4 链表示意：

输入:  4 -> 2 -> 1 -> 3 -> null
head = 4
输出:  1 -> 2 -> 3 -> 4 -> null

text

说明： 把链表节点按升序重新排列后，结果就是 1 -> 2 -> 3 -> 4。

补充说明#

链表题的输入本质上是节点之间的连接关系，重点通常是返回处理后的头节点或目标节点。

问题的本质#

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

plaintext

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

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

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

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

找中点的艺术#

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

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

分治排序的实现#

public ListNode sortList(ListNode head) {
    // 递归终止：空链表或单节点天然有序
    if (head == null || head.next == null) {
        return head;
    }

    // 1) 快慢指针找中点：slow 走1步，fast 走2步
    ListNode slow = head;
    // fast 从 head.next 起步，可让 slow 停在“左半部分尾节点”
    ListNode fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    // 2) 断开链表：head..slow 为左半，secondHalf..end 为右半
    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) {
    // dummy：哨兵节点，简化头节点拼接逻辑
    ListNode dummy = new ListNode(0);
    // curr：结果链表当前尾节点
    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;
}

java

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

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

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

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

迭代归并排序实现#

public ListNode sortList(ListNode head) {
    // 边界处理：空链表或单节点无需排序
    if (head == null || head.next == null) {
        return head;
    }

    // 1) 先统计链表长度，决定外层 step 的迭代次数
    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) {
        // prev：已完成合并部分的尾节点
        ListNode prev = dummy;
        // curr：当前待处理位置
        curr = dummy.next;

        while (curr != null) {
            // 3.1 切出长度为 step 的左子链表
            ListNode left = curr;
            // 3.2 再切出长度为 step 的右子链表
            ListNode right = split(left, step);
            // 3.3 curr 指向下一段尚未处理的起点
            curr = split(right, step);

            // 3.4 合并 left/right，并更新 prev 到合并后尾部
            prev = merge(left, right, prev);
        }
    }

    // 返回排序后真实头节点
    return dummy.next;
}

// 分割函数：向前数n个节点，返回下一个节点，并断开连接
private ListNode split(ListNode head, int n) {
    // 走到第 n 个节点（或提前到 null）
    while (--n > 0 && head != null) {
        head = head.next;
    }

    // rest：被切割后剩余部分的头节点
    ListNode rest = (head != null) ? head.next : null;
    // 断开前一段，形成独立子链表
    if (head != null) head.next = null;
    return rest;
}

// 合并函数：合并两个有序链表，返回合并后的尾节点
private ListNode merge(ListNode l1, ListNode l2, ListNode prev) {
    // curr 从 prev 出发，把合并结果接在 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;
    // 向后走到当前合并段的最后一个节点，作为返回的新 prev
    while (curr.next != null) {
        curr = curr.next;
    }

    // 返回合并后尾节点，供外层继续连接后续分段
    return curr;
}

java

复杂度分析与比较#

自顶向下的归并排序：

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

自底向上的归并排序：

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

技巧总结#

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

实际应用延伸#

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

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

小结#

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

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

这道题的启示：

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

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