vvrf / DSA.log

问题拆解

对链表做升序排序，要求 O(n log n) 时间。把节点值倒进数组排完再写回去当然可行，但多了 O(n) 空间，也失去了链表题的意义。在 O(n log n) 的排序家族里挑一个：快排依赖随机访问选轴、堆排要下标计算，都和链表八字不合；归并排序不同——它的三个子动作“对半分、递归、合并有序段”在链表上一个比一个自然，合并甚至比数组还省（改指针即可，不用挪元素）。

对半分靠快慢指针：快指针一次两步、慢指针一次一步，快到尾时慢在中点，断开 slow.next 就得到两条独立的子链。

归并排序的数组版短板在合并要开辅助数组，链表版恰好没有这个负担——合并两条有序链表（21 题）是 O(1) 额外空间的。分治骨架 + 21 题的合并，就是完整解法。

快慢指针断链 + 递归归并

public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode slow = head, fast = head.next; // fast 领先一步，保证 slow 停在左半段末尾
    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));
}

private ListNode merge(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode();
    ListNode tail = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            tail.next = l1;
            l1 = l1.next;
        } else {
            tail.next = l2;
            l2 = l2.next;
        }
        tail = tail.next;
    }
    tail.next = l1 != null ? l1 : l2;
    return dummy.next;
}

def sortList(head):
    if head is None or head.next is None:
        return head
    slow, fast = head, head.next  # fast 领先一步，保证 slow 停在左半段末尾
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    mid = slow.next
    slow.next = None  # 断链，两半各自独立
    return merge(sortList(head), sortList(mid))


def merge(l1, l2):
    dummy = ListNode()
    tail = dummy
    while l1 and l2:
        if l1.val <= l2.val:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next
    tail.next = l1 if l1 else l2
    return dummy.next

func sortList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    slow, fast := head, head.Next // fast 领先一步，保证 slow 停在左半段末尾
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    mid := slow.Next
    slow.Next = nil // 断链，两半各自独立
    return mergeLists(sortList(head), sortList(mid))
}

func mergeLists(l1, l2 *ListNode) *ListNode {
    dummy := &ListNode{}
    tail := dummy
    for l1 != nil && l2 != nil {
        if l1.Val <= l2.Val {
            tail.Next = l1
            l1 = l1.Next
        } else {
            tail.Next = l2
            l2 = l2.Next
        }
        tail = tail.Next
    }
    if l1 != nil {
        tail.Next = l1
    } else {
        tail.Next = l2
    }
    return dummy.Next
}

// Rust 里快慢指针要同时持有两个可变借用，改用先数长度再按 len/2 断链，
// take() 摘下右半段后两条链所有权独立，递归可以安全进行。
pub fn sort_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    let mut len = 0;
    let mut p = head.as_ref();
    while let Some(node) = p {
        len += 1;
        p = node.next.as_ref();
    }
    Self::merge_sort(head, len)
}

fn merge_sort(mut head: Option<Box<ListNode>>, len: usize) -> Option<Box<ListNode>> {
    if len <= 1 {
        return head;
    }
    let mut cur = head.as_mut().unwrap();
    for _ in 0..len / 2 - 1 {
        cur = cur.next.as_mut().unwrap();
    }
    let right = cur.next.take(); // 断链，右半段所有权被拿走
    let left = Self::merge_sort(head, len / 2);
    let right = Self::merge_sort(right, len - len / 2);
    Self::merge(left, right)
}

fn merge(mut l1: Option<Box<ListNode>>, mut l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    let mut dummy = Box::new(ListNode::new(0));
    let mut tail = &mut dummy;
    while l1.is_some() && l2.is_some() {
        let source = if l1.as_ref().unwrap().val <= l2.as_ref().unwrap().val {
            &mut l1
        } else {
            &mut l2
        };
        let mut node = source.take().unwrap();
        *source = node.next.take();
        tail.next = Some(node);
        tail = tail.next.as_mut().unwrap();
    }
    tail.next = l1.or(l2);
    dummy.next
}

最隐蔽的坑在快指针的起点：fast 必须从 head.next 出发而不是 head。考虑只有两个节点的链表，若 fast 从 head 起步，循环结束时 slow 停在第二个节点，断链后左半是整条链、右半为空，递归规模不减，直接栈溢出。让 fast 领先一步，slow 才会停在左半段的末尾，保证每次都是真正的对半分。

另一个细节是断链本身：忘了 slow.next = null（Rust 里是 take()），左半段递归时会一路走到原链表尾部，两半根本没有分开。合并部分与 21 题逐字相同，<= 保持稳定性。

复杂度

指标	复杂度	原因
时间	`O(n log n)`	递归 log n 层，每层找中点 + 合并共 O(n)
空间	`O(log n)`	递归栈深度；合并本身只改指针

可以迁移的模式

数据结构决定排序算法：不能随机访问就想归并，合并有序段只依赖顺序遍历；
快慢指针找中点时，用 fast = head.next 起步让分割偏向左小右大，规避两元素的死循环；
分治前先“断干净”，让子问题在物理上独立，递归才不会互相越界。

“找中点、断开、递归、合并”四步是链表分治的完整模板，148 是它最纯粹的用例。