1 题目

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

示例 1：

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

示例 2：

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

示例 3：

输入： head = [] 输出：[]

---

2 题解

2.1 辅助数组

2.1.1 核心思想

一句话核心：把链表问题，转化为数组问题求解。

链表的软肋是不能随机访问、不好排序；数组的强项是支持随机访问、排序成熟高效。

所以我们采用迂回策略：

摘节点 → 数组排序 → 重新串成****链表

不改动节点数据、不新建节点，只改变「指针的连接顺序」。

2.1.2 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        vector<pair<int, ListNode*>> pil;
        ListNode* cur = head;
        while(cur) {
            pil.push_back({cur->val, cur});
            cur = cur->next;
        }
        sort(pil.begin(), pil.end(), [](pair<int, ListNode*>& p1, pair<int, ListNode*>p2) {
            return p1.first < p2.first;
        });
        ListNode dummy = ListNode(0);
        ListNode* tail = &dummy;
        for(auto node: pil) {
            tail->next = node.second;
            tail = tail->next;
        }
        tail->next = nullptr;
        return dummy.next;
    }
};

2.1.3 复杂度

时间复杂度：$O(n\log n)$，sort的时间；遍历链表两次$O(n)$ 空间复杂度：$O(n)$，vector 存了全部节点指针

2.2 自顶向下归并排序（递归版）

2.2.1 核心思想

1. 分割：快慢指针找到链表中点，切断链表拆成左右两部分
2. 左递归：递归对左子链表执行排序
3. 右递归：递归对右子链表执行排序
4. 合并：将排序完成的左右两条有序链表合并为一条，向上返回

递归终止条件是基础保护：if(!head || !head->next) return head;，不属于这 4 行核心业务逻辑。

2.2.2 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(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* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* cur = &dummy;
        while(l1 && l2) {
            if(l1->val < l2->val) {
                cur->next = l1;
                l1 = l1->next;
            } else {
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        cur->next = l1 ? l1 : l2;
        return dummy.next;
    }
};

2.2.3 复杂度

时间复杂度：$O(n\log n)$ 空间复杂度：$O(\log n)$（递归调用栈）

2.3 自底向上归并排序（迭代版）

2.3.1 核心思想

1. 测长度：先遍历一遍统计链表总长度，决定需要合并几轮
2. 外层轮数：合并段长 seg 从 1 开始，每轮翻倍（1、2、4、8…），直到 seg ≥ length 覆盖整条链表
3. 内层合并：把链表按 seg 长度切成一段段，相邻两段 merge 成一个更大的有序段，每轮把整条链表重连一遍
4. 返回结果：所有轮次结束，整条链表完全有序，返回头节点

辅助函数：cut(head, k) 截断前 k 个节点并返回下一段起点；merge(l1, l2) 合并两条有序链表。这两个不属于核心思想，但写代码必须要有。

2.3.2 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(!head || !head->next) {
            return head;
        }
        int length = 0;
        ListNode* cur = head;
        while(cur) {
            length++;
            cur = cur->next;
        }
        ListNode dummy(0);
        dummy.next = head;
        for(int seg = 1; seg < length; seg <<= 1) {
            ListNode* tail = &dummy;
            ListNode* cur = dummy.next;
            while(cur) {
                ListNode* left = cur;
                ListNode* right = cut(cur, seg);
                cur = cut(right, seg);
                tail->next = merge(left, right);
                while(tail->next) {
                    tail = tail->next;
                }
            }
        }
        return dummy.next;
    }

    ListNode* cut(ListNode* head, int k) {
        while(--k && head) {
            head = head->next;
        }
        if (!head) return nullptr;
        ListNode* next_start = head->next;
        head->next = nullptr;
        return next_start;
    }

    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* cur = &dummy;
        while(l1 && l2) {
            if(l1->val < l2->val) {
                cur->next = l1;
                l1 = l1->next;
            } else {
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        cur->next = l1 ? l1 : l2;
        return dummy.next;
    }
};

2.3.3 复杂度

时间复杂度：$O(n\log n)$ 空间复杂度：$O(1)$

2.4 三种算法对比

方案	核心思路	时间复杂度	空间复杂度	代码难度	核心特点
辅助数组法	遍历链表收集节点指针，数组排序后重新串联节点，空间换简单	O(nlogn)	O(n)	⭐	笔试速通首选；需要处理尾节点置空，否则链表成环，不满足进阶 O (1) 空间
自顶向下归并（递归）	分治，快慢指针二分拆链表，递归排序左右子链表，最后合并有序链表；先拆后合	O(nlogn)	O(logn)（递归栈）	⭐⭐	面试最常考，代码简洁好写；递归栈占用空间，无法做到严格常数空间
自底向上归并（迭代）	迭代，从长度为 1 的有序小段开始两两合并，段长不断翻倍直至整条链表有序；从小段到大段合并	O(nlogn)	O(1)	⭐⭐⭐	本题最优解，无递归，满足进阶 O (1) 空间；需要实现 cut 截断函数，逻辑稍复杂

3 148. 排序链表 - 力扣（LeetCode）