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
)
O(n\\log n)
O(nlogn)，sort的时间；遍历链表两次
O
(
n
)
O(n)
O(n) 空间复杂度：
O
(
n
)
O(n)
O(n)，vector 存了全部节点指针
2.2 自顶向下归并排序（递归版）
2.2.1 核心思想
递归终止条件是基础保护：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(n\\log n)
O(nlogn) 空间复杂度：
O
(
log
n
)
O(\\log n)
O(logn)（递归调用栈）
2.3 自底向上归并排序（迭代版）
2.3.1 核心思想
辅助函数：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(n\\log n)
O(nlogn) 空间复杂度：
O
(
1
)
O(1)
O(1)
2.4 三种算法对比
| 辅助数组法 | 遍历链表收集节点指针，数组排序后重新串联节点，空间换简单 | O(nlogn) | O(n) | ⭐ | 笔试速通首选；需要处理尾节点置空，否则链表成环，不满足进阶 O (1) 空间 |
| 自顶向下归并（递归） | 分治，快慢指针二分拆链表，递归排序左右子链表，最后合并有序链表；先拆后合 | O(nlogn) | O(logn)（递归栈） | ⭐⭐ | 面试最常考，代码简洁好写；递归栈占用空间，无法做到严格常数空间 |
| 自底向上归并（迭代） | 迭代，从长度为 1 的有序小段开始两两合并，段长不断翻倍直至整条链表有序；从小段到大段合并 | O(nlogn) | O(1) | ⭐⭐⭐ | 本题最优解，无递归，满足进阶 O (1) 空间；需要实现 cut 截断函数，逻辑稍复杂 |
