排序链表 图解题解

为什么链表排序首选归并排序

在 O(n log n) 的几大排序里，堆排序要按下标随机访问，链表做不到；快速排序依赖来回交换元素，链表上实现别扭且最坏会退化到 O(n²)。归并排序的两个核心动作——从中间劈开、把两条有序序列合并——恰好都是链表擅长的顺序操作。更妙的是，数组版归并需要 O(n) 辅助数组存放合并结果，链表版只需把现成节点重新接线，一个新节点都不用建，归并排序在链表上反而比在数组上更省。

快慢指针找中点，fast 为什么从 head.next 出发

找中点用快慢指针：slow 每次走一步、fast 每次走两步，fast 到尾时 slow 停在中间附近。细节在起点：fast 从 head.next 出发而不是 head，这样偶数长度时 slow 停在左半的末尾，劈出来的左半不长于右半、且两半都非空。若 fast 从 head 出发，长度为二的链会被劈成「整条加空链」，子问题规模没有变小，递归永远到不了底。

劈开之后为什么必须把链断掉

找到中点后要做两件事：记下右半的头 mid，并把左半末尾的 next 置空，也就是代码里的 slow.next = None。断链这一步最容易漏——不置空的话，左半在物理上仍然连着右半，对左半递归时快慢指针会一路跑进右半，子问题没有缩小，结果就是死循环或者栈溢出。断干净之后，左右两条子链才是彼此独立的更小问题，递归才能收敛到单节点这个天然有序的终点。

合并两条有序链为什么是对的

合并阶段用一个哨兵节点起头，反复比较两条链的头节点，把较小者摘下来接到结果尾部，某一条走完后把另一条整段接上。正确性来自两条链各自有序：两个头当中较小的那个，必然小于等于双方剩余的所有节点，把它放到结果的下一个位置不可能出错。值相等时优先取左半的节点（比较用小于等于），能让相同元素保持原有先后，也就是稳定排序。

复杂度怎么数，空间还能再省吗

每层递归把链劈成两半，共约 log n 层；每一层的全部合并加起来恰好扫 n 个节点，总时间 O(n log n)。合并不新建节点，额外开销只剩递归调用栈的 O(log n)。想做到严格 O(1) 空间，可以改成自底向上的迭代写法：先按子段长度一两两合并，再按二、四逐层翻倍，用循环替代递归，逻辑同构但不吃栈空间——这是本题最常见的面试追问。

Python

def sortList(head):
    if not head or not head.next: return head
    slow, fast = head, head.next        # 快慢指针找中点
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    mid = slow.next; slow.next = None    # 从中点断开
    left, right = sortList(head), sortList(mid)
    dummy = tail = ListNode()            # 合并两条有序链
    while left and right:
        if left.val <= right.val:
            tail.next, left = left, left.next
        else:
            tail.next, right = right, right.next
        tail = tail.next
    tail.next = left or right
    return dummy.next

C++

ListNode* sortList(ListNode* head){
    if(!head || !head->next) return head;
    ListNode *slow=head, *fast=head->next;
    while(fast && fast->next){ slow=slow->next; fast=fast->next->next; }
    ListNode* mid=slow->next; slow->next=nullptr;
    ListNode *l=sortList(head), *r=sortList(mid);
    ListNode dummy, *tail=&dummy;
    while(l && r){
        if(l->val <= r->val){ tail->next=l; l=l->next; }
        else { tail->next=r; r=r->next; }
        tail=tail->next;
    }
    tail->next = l ? l : r;
    return dummy.next;
}

Java

public ListNode sortList(ListNode head){
    if(head == null || head.next == null) return head;
    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;
    ListNode left = sortList(head), right = sortList(mid);
    ListNode dummy = new ListNode(0), tail = dummy;
    while(left != null && right != null){
        if(left.val <= right.val){ tail.next = left; left = left.next; }
        else { tail.next = right; right = right.next; }
        tail = tail.next;
    }
    tail.next = (left != null) ? left : right;
    return dummy.next;
}