148. 排序链表

📝 题目描述

给定链表的头节点 head，要求将其按升序排列并返回排序后的链表。

📌 示例

示例 1

输入：head = [4,2,1,3] 输出：[1,2,3,4]

示例 2

输入：head = [-1,5,3,4,0] 输出：[-1,0,3,4,5]

🚀 最优解：归并排序（分治法）

🔍 思路解析

核心策略：利用分治思想，将链表拆分为子链表，排序后再合并，时间复杂度为 (O(n \log n))（链表排序的最优时间复杂度）：

1. 拆分链表：用快慢指针找到链表的中点，将链表拆分为左右两部分；
2. 递归排序：对左右两部分子链表分别递归执行排序；
3. 合并链表：将排序后的左右子链表合并为一个升序链表。

---

✅ 完整代码（Java）

import java.util.Scanner;

public class Main {
    private static ListNode buildList(String line) {
        if (line == null) {
            return null;
        }
        line = line.trim();
        if (line.isEmpty()) {
            return null;
        }
        String[] values = line.split(" ");
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        for (String val : values) {
            if (val.isEmpty()) {
                continue;
            }
            tail.next = new ListNode(Integer.parseInt(val));
            tail = tail.next;
        }
        return dummy.next;
    }

    private static void printList(ListNode head) {
        StringBuilder sb = new StringBuilder();
        while (head != null) {
            sb.append(head.val);
            if (head.next != null) {
                sb.append(" ");
            }
            head = head.next;
        }
        System.out.println(sb.toString());
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String line = scanner.hasNextLine() ? scanner.nextLine() : "";
        ListNode head = buildList(line);

        Solution solution = new Solution();
        ListNode result = solution.sortList(head);
        printList(result);
        scanner.close();
    }
}

class Solution {
    public ListNode sortList(ListNode head) {
        // 递归终止条件：空链表或单个节点（已有序）
        if (head == null || head.next == null) {
            return head;
        }
        // 找到链表中点
        ListNode mid = searchMid(head);
        ListNode rightHead = mid.next;
        mid.next = null; // 拆分左右链表
        
        // 递归排序左右子链表
        ListNode left = sortList(head);
        ListNode right = sortList(rightHead);
        
        // 合并排序后的子链表
        return mergeTwoSortedList(left, right);
    }

    // 快慢指针找链表中点（偶数长度时取左中点）
    private ListNode searchMid(ListNode head) {
        ListNode fast = head.next;
        ListNode slow = head;
        // fast每次走2步，slow每次走1步，fast到尾时slow在中点
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    // 合并两个升序链表
    private ListNode mergeTwoSortedList(ListNode left, ListNode right) {
        ListNode dummy = new ListNode(0); // 虚拟头节点
        ListNode cur = dummy;
        // 双指针遍历，选择较小值接入新链表
        while (left != null && right != null) {
            if (left.val < right.val) {
                cur.next = left;
                left = left.next;
            } else {
                cur.next = right;
                right = right.next;
            }
            cur = cur.next;
        }
        // 接入剩余节点
        cur.next = (left != null) ? left : right;
        return dummy.next;
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

---

🧠 通俗易懂解释

可以把链表想象成“一串无序的珠子”，排序过程类似先拆成小串、各自排好序，再串成一串有序的：

1. 拆分：用快慢指针把珠子串拆成左右两小串；
2. 子串排序：对每小串重复拆分、排序的操作，直到每小串只有1颗珠子（天然有序）；
3. 合并：把排好序的小串两两合并，最终得到完整的有序串。

以示例1（head = [4,2,1,3]）为例：

1. 拆分中点为 2，链表拆分为 [4,2] 和 [1,3]；
2. 递归拆分 [4,2] 为 [4] 和 [2]，排序后合并为 [2,4]； 递归拆分 [1,3] 为 [1] 和 [3]，排序后合并为 [1,3]；
3. 合并 [2,4] 和 [1,3]，得到最终有序链表 [1,2,3,4]。

---

⏱ 时间复杂度

• (O(n \log n))（n 为链表长度） 拆分链表的时间为 (O(\log n)) 层，每层合并的时间为 (O(n))，整体复杂度为 (O(n \log n))。

---

💾 空间复杂度

• (O(\log n)) 递归调用栈的深度为拆分的层数 (O(\log n))，额外空间主要用于递归栈。