排序链表
**给你链表的头节点 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 = []
输出：[]
提示：
- 链表中节点的数目在范围
[0, 5 * 10^4]内 -10^5 <= Node.val <= 10^5
进阶：
你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
解法一（递归归并排序）：
/**
* 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 == nullptr || head->next == nullptr)
{
return head;
}
ListNode* slow = head;
ListNode* fast = head->next;
while (fast != nullptr && fast->next != nullptr)
{
slow = slow->next;
fast = fast->next->next;
}
ListNode* rightHead = slow->next;
slow->next = nullptr;
ListNode* left = sortList(head);
ListNode* right = sortList(rightHead);
return merge(left, right);
}
private:
ListNode* merge(ListNode* list1, ListNode* list2) {
ListNode dummy(0);
ListNode* tail = &dummy;
while (list1 != nullptr && list2 != nullptr)
{
if (list1->val <= list2->val)
{
tail->next = list1;
list1 = list1->next;
}
else
{
tail->next = list2;
list2 = list2->next;
}
tail = tail->next;
}
tail->next = list1 != nullptr ? list1 : list2;
return dummy.next;
}
};
解法二（自底向上归并排序）：
/**
* 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 == nullptr || head->next == nullptr)
{
return head;
}
int length = 0;
ListNode* cur = head;
while (cur != nullptr)
{
length++;
cur = cur->next;
}
ListNode dummy(0, head);
for (int subLen = 1; subLen < length; subLen <<= 1)
{
ListNode* prev = &dummy;
cur = dummy.next;
while (cur != nullptr)
{
ListNode* head1 = cur;
ListNode* head2 = split(head1, subLen);
cur = split(head2, subLen);
prev->next = merge(head1, head2);
while (prev->next != nullptr)
{
prev = prev->next;
}
}
}
return dummy.next;
}
private:
ListNode* split(ListNode* head, int size) {
if (head == nullptr)
{
return nullptr;
}
for (int i = 1; i < size && head->next != nullptr; i++)
{
head = head->next;
}
ListNode* second = head->next;
head->next = nullptr;
return second;
}
ListNode* merge(ListNode* list1, ListNode* list2) {
ListNode dummy(0);
ListNode* tail = &dummy;
while (list1 != nullptr && list2 != nullptr)
{
if (list1->val <= list2->val)
{
tail->next = list1;
list1 = list1->next;
}
else
{
tail->next = list2;
list2 = list2->next;
}
tail = tail->next;
}
tail->next = list1 != nullptr ? list1 : list2;
return dummy.next;
}
};
核心思想
链表排序最适合使用归并排序。
原因是链表不像数组那样可以随机访问，快速排序或堆排序在链表上并不方便。
归并排序只需要做两件事：
- 把链表拆成两段
- 把两个已经有序的链表合并成一个有序链表
合并两个有序链表对链表来说非常自然，只需要调整 next 指针即可。
这题最关键的观察是：
链表不能高效随机访问，但可以很方便地断开、拼接和合并，所以归并排序是链表排序的常用做法。
递归归并排序写起来更直观，但递归调用栈需要 O(log n) 空间。
进阶要求常数级空间，所以更推荐自底向上的迭代归并排序。
解法一：递归归并排序
递归归并排序分三步。
1. 找到链表中点
使用快慢指针：
slow每次走一步fast每次走两步
当 fast 到达链表末尾时，slow 大致位于链表中间。
代码中初始化为：
ListNode* slow = head;
ListNode* fast = head->next;
这样在偶数长度链表中，slow 会停在左半段的最后一个节点，方便断开链表。
2. 断开左右两段
找到中点后：
ListNode* rightHead = slow->next;
slow->next = nullptr;
左半段从 head 开始。
右半段从 rightHead 开始。
断开以后，两段链表可以分别递归排序。
3. 合并两个有序链表
递归排序左右两段：
ListNode* left = sortList(head);
ListNode* right = sortList(rightHead);
然后把两个有序链表合并：
return merge(left, right);
合并过程和“合并两个有序链表”一样，每次取两个链表当前头节点中较小的那个接到结果后面。
解法二：自底向上归并排序
递归归并排序的问题是递归栈不满足常数空间要求。
自底向上归并排序不使用递归，而是从长度为 1 的小段开始合并。
具体过程是：
长度 1 的有序段两两合并 -> 长度 2
长度 2 的有序段两两合并 -> 长度 4
长度 4 的有序段两两合并 -> 长度 8
...
每一轮的子链表长度是 subLen。
每轮结束后：
subLen <<= 1
直到 subLen >= length，整个链表就已经有序。
split 函数做什么
split(head, size) 的作用是：
- 从
head开始截出长度最多为size的一段链表 - 把这段链表和后面的部分断开
- 返回下一段链表的头节点
例如：
1 -> 4 -> 2 -> 3
当 size = 2 时，从 1 开始截出：
1 -> 4
返回下一段的头节点：
2
同时把第一段末尾的 next 置为 nullptr。
这样后续 merge 时，每一段都是独立链表，不会串到后面的未处理节点。
为什么自底向上是常数空间
递归归并排序需要递归调用栈。
自底向上归并排序用循环控制段长度和当前位置，只使用：
dummyprevcurhead1head2
这些指针变量。
没有使用额外数组，也没有递归调用栈。
所以如果不把原链表节点本身计入额外空间，它的空间复杂度是 O(1)。
边界情况
如果链表为空：
head = []
直接返回 nullptr。
如果链表只有一个节点，已经有序，直接返回 head。
如果链表中有重复值，例如：
head = [1,1,1]
归并时使用：
list1->val <= list2->val
可以正常处理相等节点，结果仍然是升序链表。
如果链表长度不是 2 的整数次幂，自底向上归并中最后一段长度可能不足 subLen。
split 会自然截出剩余部分，不需要额外特殊处理。
正确性证明
我们证明：归并排序返回的链表按升序排列，并且包含原链表中的所有节点。
结论 1：merge 能把两个有序链表合并成一个有序链表
合并时，每次比较两个链表当前头节点。
较小的节点一定是两个链表所有未处理节点中的最小值。
把它接到结果链表末尾，不会破坏升序。
重复这个过程，直到某个链表为空。
剩余链表本身已经有序，可以直接接到结果末尾。
因此 merge 返回的链表是升序的，并且包含两个输入链表的全部节点。
结论 2：递归归并排序能正确排序任意长度链表
当链表为空或只有一个节点时，它本身已经有序，直接返回正确。
当链表长度大于 1 时，算法把链表拆成左右两段。
根据递归假设，左右两段经过 sortList 后分别有序。
再根据结论 1，把两个有序链表合并后，得到的整条链表也是有序的。
因此递归归并排序正确。
结论 3：自底向上归并每一轮后，长度为 subLen 的连续段都是有序的
初始时，subLen = 1。
每个单独节点都可以看成一个有序段。
一轮合并中，算法每次取出两个长度最多为 subLen 的有序段，并用 merge 合并成一个长度最多为 2 * subLen 的有序段。
根据结论 1，合并后的段仍然有序。
所以这一轮结束后，长度为 2 * subLen 的连续段都是有序的。
结论 4：自底向上归并结束时，整个链表有序
每一轮都会让有序段长度翻倍。
当 subLen >= length 时，整个链表已经被视为一个有序段。
因此最终返回的链表整体升序排列。
得出结论
由结论 1 可知，合并两个有序链表的过程正确。
由结论 2 可知，递归归并排序正确。
由结论 3 和结论 4 可知，自底向上归并排序正确。
因此两个解法都能返回排序后的链表。
举例理解
以：
head = [4,2,1,3]
为例。
递归归并排序会先拆成：
[4,2] 和 [1,3]
继续拆：
[4] [2] [1] [3]
然后两两合并：
[2,4] 和 [1,3]
最后合并：
[1,2,3,4]
所以返回：
[1,2,3,4]
复杂度分析
解法一
每一层递归都会遍历链表进行拆分和合并。
递归层数是 O(log n)。
- 时间复杂度：
O(n log n) - 空间复杂度：
O(log n)
其中空间复杂度来自递归调用栈。
解法二
自底向上归并排序每一轮都会遍历链表一次。
一共需要 O(log n) 轮。
- 时间复杂度：
O(n log n) - 空间复杂度：
O(1)
解法二满足进阶要求，是更推荐的做法。**