148. 排序链表

难度：🟡 Medium | 标签：链表、归并排序 | 状态：⬜ LeetCode 链接

思路

链表归并排序：

1. 快慢指针找中点，切两半
2. 递归各排各
3. 合并（同 21 题）

题目要求 O(n log n) 且 O(1) 空间——严格意义下要写自底向上迭代版，递归是 O(log n) 栈，面试递归版即可。

代码

class Solution {
public:
    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* right = slow->next;
        slow->next = nullptr;
        return merge(sortList(head), sortList(right));
    }
private:
    ListNode* merge(ListNode* a, ListNode* b) {
        ListNode dummy(0), *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;
    }
};

复杂度

• 时间 O(n log n)，空间 O(log n)（递归栈）

易错 / 回顾

• 找中点时 fast = head->next，保证奇数切分两边平衡
• 切完一定要 slow->next = nullptr，否则左半段还连着右半
• 自底向上迭代版才是严格 O(1) 空间，但代码长 2 倍