排序链表 图解题解

这道题到底在问什么

输入

4→2→1→3

输出

1→2→3→4

最优解：一步一步想明白

1. 3数组排序爱用快排，靠下标左右跳。可链表只能一根一根顺着走，没有下标，快排的随机访问就废了。
2. 4归并排序天生适合链表：它只要能顺着 next 往后走、再把节点一个个接起来。这两件事链表都很擅长，所以选它。
3. 5把长链表劈成两半，各自排好，再合并归并三步：先把链表从中间切成两半，递归地各自排好序，最后把两条有序链表合并成一条。下面慢放这三步。
4. 6slow 走 1 步，fast 走 2 步slow 从第 1 个出发，fast 从第 2 个出发。fast 每次跳 2 步、slow 每次跳 1 步，fast 到尾巴时 slow 正好停在前半段的末尾。
5. 7slow→节点2，fast→节点3，fast.next 为空，停走一轮：slow 跳到值 2，fast 跳到值 3。再看 fast.next 已经是空，循环停下。此刻 slow 停在前半段的最后一个节点 2 上。
6. 8mid = slow.next = 节点1；slow.next 置空mid 记下 slow 后面那个节点（值 1），再把 slow.next 剪成空。一刀下去，链表断成左半 4→2 和右半 1→3 两条独立的链。
7. 9左半再切：4 一段、2 一段，合并出 2→4对左半 4→2 再递归：切成单个 4 和单个 2，单节点天然有序，合并时 2＜4，所以接成 2→4。左半排好了。
8. 10右半同样切半再合并，得到 1→3右半 1→3 同样切半再合并，1＜3 本就有序，得到 1→3。现在两条短链都各自有序，准备合并。
9. 111 ＜ 2，把 1 接到结果，右半头后移合并开始：比左半头 2 和右半头 1。1 更小，把 1 接到结果链尾，右半的 b 指针往后挪到 3。
10. 122 ＜ 3，把 2 接到结果，左半头后移再比：左半头 2 和右半头 3，2 更小。把 2 接上结果，左半的 a 指针挪到 4。结果链现在是 1→2。
11. 133 ＜ 4，把 3 接到结果，右半走空继续比：左半头 4 和右半头 3，3 更小。接上 3，右半走到头变空。结果链是 1→2→3，只剩左半的 4 还没接。
12. 14一边空了，直接把另一边整条接上右半空了，左半还剩一个 4。归并的收尾招：哪边没走完，就把它整条直接接到结果尾巴。最终得到 1→2→3→4，排序完成。
13. 17一句话本质：把长链对半切到不能再切，再一层层合并回来。链表只用得着「往后走」和「接节点」，所以归并最顺手。
14. 19若 slow、fast 都从 head 起步，两节点切不开拿两节点 4→2 试：若 slow、fast 都从头起步，fast 跳到 2、fast.next 为空就停，slow 还停在 4。mid 仍是整条、左半也是整条，根本没切开，递归会原地打转。所以 fast 必须从 head.next 起步。
15. 23这题是两个基本功的组合：第 876 题「链表中间结点」练快慢指针切半，第 21 题「合并两个有序链表」练合并，吃透它们，本题就是把两者拼起来。卡住可以问问 AI 助教小欧，或去链表专题通关训练。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def sortList(self, head):
        if not head or not head.next:
            return head
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        mid = slow.next
        slow.next = None
        left = self.sortList(head)
        right = self.sortList(mid)
        return self.merge(left, right)
    def merge(self, a, b):
        dummy = tail = ListNode(0)
        while a and b:
            if a.val < b.val:
                tail.next, a = a, a.next
            else:
                tail.next, b = b, b.next
            tail = tail.next
        tail.next = a or b
        return dummy.next

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode* slow = head;
        ListNode* fast = head->next;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode* mid = slow->next;
        slow->next = nullptr;
        ListNode* left = sortList(head);
        ListNode* right = sortList(mid);
        return merge(left, right);
    }
    ListNode* merge(ListNode* a, ListNode* b) {
        ListNode dummy(0);
        ListNode* tail = &dummy;
        while (a && b) {
            if (a->val < b->val) {
                tail->next = a; a = a->next;
            } else {
                tail->next = b; b = b->next;
            }
            tail = tail->next;
        }
        tail->next = a ? a : b;
        return dummy.next;
    }
};

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode mid = slow.next;
        slow.next = null;
        ListNode left = sortList(head);
        ListNode right = sortList(mid);
        return merge(left, right);
    }
    private ListNode merge(ListNode a, ListNode b) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while (a != null && b != null) {
            if (a.val < b.val) {
                tail.next = a; a = a.next;
            } else {
                tail.next = b; b = b.next;
            }
            tail = tail.next;
        }
        tail.next = (a != null) ? a : b;
        return dummy.next;
    }
}

def sortList(head):
    # 边界：空或单节点直接返回
    if not head or not head.next:
        return head
    # ① 快慢指针找中点（fast 从 head.next 起）
    slow, fast = head, head.next
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    # ② 断开：记下右半头，剪断左半尾
    mid = slow.next
    slow.next = None
    # ③ 递归排两半，再合并
    return merge(sortList(head), sortList(mid))

ListNode* sortList(ListNode* head) {
    // 边界：空或单节点直接返回
    if (!head || !head->next) return head;
    // ① 快慢指针找中点（fast 从 head->next 起）
    ListNode *slow = head, *fast = head->next;
    while (fast && fast->next) {
        slow = slow->next; fast = fast->next->next;
    }
    // ② 断开：记下右半头，剪断左半尾
    ListNode* mid = slow->next;
    slow->next = nullptr;
    // ③ 递归排两半，再合并
    return merge(sortList(head), sortList(mid));
}

ListNode sortList(ListNode head) {
    // 边界：空或单节点直接返回
    if (head == null || head.next == null) return head;
    // ① 快慢指针找中点（fast 从 head.next 起）
    ListNode slow = head, fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next; fast = fast.next.next;
    }
    // ② 断开：记下右半头，剪断左半尾
    ListNode mid = slow.next;
    slow.next = null;
    // ③ 递归排两半，再合并
    return merge(sortList(head), sortList(mid));
}

复杂度

面试官可能追问