#148

中等

中频

归并排序

排序链表

这是一道围绕链表、排序展开的高频练习。建议先掌握「归并排序」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。

链表

排序

原题练习

题目分析

这道题表面上是在处理「排序链表」，但先要想清楚题目到底让你返回什么，以及过程中哪些约束必须一直满足。从题型上看，它主要在考链表、排序这些能力。先别急着写代码，先把题目要求翻译成人话，明确结果是什么、约束是什么、过程里要持续维护什么。只有先把题目要求翻译成人话，后面的推荐代码才是在实现思路，而不是直接给答案。

接下来怎么看推荐代码：带着这个理解再看推荐代码时，重点观察这条主线：用快慢指针把链表拆成两半，分别排序后再按有序链表归并起来。

推荐代码

推荐解法：归并排序

时间复杂度： O(n log n)

空间复杂度： O(log n)

核心思路：用快慢指针把链表拆成两半，分别排序后再按有序链表归并起来。

// 排序链表 - 归并排序算法
// 时间复杂度：O(n log n)
// 空间复杂度：O(log n)

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) {
        return sortList(head, null);
    }

    // 辅助函数：对从head到tail（不包含tail）的链表进行排序
    public ListNode sortList(ListNode head, ListNode tail) {
        // 边界情况：如果链表为空，直接返回
        if (head == null) {
            return head;
        }
        // 边界情况：如果链表只有一个节点，将其next设为null并返回
        if (head.next == tail) {
            head.next = null;
            return head;
        }
        // 使用快慢指针找到链表的中点
        ListNode slow = head, fast = head;
        while (fast != tail) {
            slow = slow.next;
            fast = fast.next;
            if (fast != tail) {
                fast = fast.next;
            }
        }
        // 中点即为slow
        ListNode mid = slow;
        // 递归排序左半部分
        ListNode list1 = sortList(head, mid);
        // 递归排序右半部分
        ListNode list2 = sortList(mid, tail);
        // 合并两个已排序的链表
        ListNode sorted = merge(list1, list2);
        return sorted;
    }

    // 合并两个已排序的链表
    public ListNode merge(ListNode head1, ListNode head2) {
        // 创建虚拟头节点，方便处理
        ListNode dummyHead = new ListNode(0);
        ListNode temp = dummyHead, temp1 = head1, temp2 = head2;
        // 比较两个链表的节点，将较小的节点添加到结果链表中
        while (temp1 != null && temp2 != null) {
            if (temp1.val <= temp2.val) {
                temp.next = temp1;
                temp1 = temp1.next;
            } else {
                temp.next = temp2;
                temp2 = temp2.next;
            }
            temp = temp.next;
        }
        // 处理剩余的节点
        if (temp1 != null) {
            temp.next = temp1;
        } else if (temp2 != null) {
            temp.next = temp2;
        }
        // 返回合并后的链表头节点（跳过虚拟头节点）
        return dummyHead.next;
    }
}

// 示例用法
public class Main {
    public static void main(String[] args) {
        // 创建一个无序链表：4->2->1->3
        ListNode head = new ListNode(4);
        head.next = new ListNode(2);
        head.next.next = new ListNode(1);
        head.next.next.next = new ListNode(3);
        
        System.out.println("原链表：");
        printList(head);
        
        // 排序链表
        Solution solution = new Solution();
        ListNode sortedHead = solution.sortList(head);
        
        System.out.println("排序后：");
        printList(sortedHead);
    }
    
    // 辅助函数：打印链表
    public static void printList(ListNode head) {
        ListNode curr = head;
        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
        System.out.println();
    }
}

结构化讲解

面试时怎么讲

开场思路

这题我会用链表归并排序，时间复杂度能做到 O(n log n)。

核心过程

先用快慢指针找到中点并把链表断成两半。
递归排序左右两段链表。
最后像合并两个有序链表那样把它们归并起来。
递归返回时，整条链表就已经有序。

复杂度总结

时间复杂度 O(n log n)，空间复杂度递归栈 O(log n)。

面试补一句：链表排序的核心理由，是“归并天然适合链表结构”。

核心思路

链表排序最适合归并排序，因为链表不支持随机访问，不适合快排式 partition；但链表的断开和归并都很自然。

步骤讲解

快慢指针找中点并断链

先把链表拆成左右两半，分别作为子问题。

为什么这样做：归并排序的第一步就是分治。

对应代码提示：ListNode mid = split(head);

递归排序左右子链表

对子链表继续执行同样的拆分与排序。

为什么这样做：两半链表和原问题结构完全相同。

对应代码提示：ListNode left = sortList(head); ListNode right = sortList(mid);

归并两个有序链表

把左右两段排序结果按升序重新拼接。

为什么这样做：归并后整体有序，递归向上即可得到完整答案。

对应代码提示：return merge(left, right);

易错点

没把链表真正断开

左右子问题会互相连着，递归无法收敛。

正确理解：找到中点后一定要把前半段尾节点 next 置空。

用数组思维做链表排序

链表不适合频繁随机交换节点。

正确理解：优先选归并排序，而不是数组式快排。

归并时没用哑节点

头节点处理容易变得混乱。

正确理解：合并有序链表时统一使用 dummy + tail 模板。

复杂度与适用判断

时间复杂度：O(n log n)

空间复杂度：O(log n)

比其他方案更好在哪里：比依赖数组拷贝再回写更贴合链表结构，也满足题目复杂度要求。

适用判断：链表题只要要求排序且追求对数级分治，优先考虑归并排序。

额外提醒

链表排序里最值钱的动作是“拆两半 + 归并”，不是交换节点。

动画演示

如果你还没完全看懂，可以展开动画演示。

归并排序动画演示

想看这段解法是怎么一步步运行的，可以展开动画继续观察。

链表值:

准备就绪 - 输入链表值（用逗号分隔），然后点击开始

动画演示仅在桌面端提供，移动端请优先阅读推荐代码与结构化讲解。