本文最后编辑于 前，其中的内容可能需要更新。
题目描述：
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
示例 1：
1
2
| 输入：head = [4,2,1,3]
输出：[1,2,3,4]
|
示例 2：
1
2
| 输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
|
示例 3：
提示：
- 链表中节点的数目在范围 $[0, 5 * 10^4]$ 内
- $-10^5 <= Node.val <= 10^5$
链接：
https://leetcode-cn.com/problems/sort-list
题目分析
题目中进阶要求我们使用 $O(n\log n)$ 时间复杂度的算法，则我们想到的有快速排序、归并排序、堆排序。而我们需要进行排序的不是数组而是链表，最适合的应该是归并排序。如何进行归并排序呢？我们可以将链表拆分成子链表，分别进行排序后再重新连接起来，而连接两个链表的算法可以使用我们前面做过的题目 Leetcode 21.合并两个有序链表。连接的时间复杂度是 $O(n)$ 的，而我们需要做 $O(\log n)$ 次归并排序，能够符合题目要求。
具体需要怎么做呢？一种是自顶向下拆分链表，递归地将链表拆分成两部分，直到变成只有单个结点，就可以视为有序的链表进行合并，慢慢地往上连接返回，但是这样需要 $O(\log n)$ 的递归空间，不能符合进阶要求中常数的空间复杂度。另一种是自底向上的方法，直接从长度 1 开始进行每两个链表的合并，然后再进行长度为 2 的每两个链表的合并（最后一个链表长度可以不用达到这个数值），以此类推直到合成一个链表。
外循环是子链表的长度 subLength，从 1 开始，每次翻倍，直到达到原链表大小（因此我们也需要先获取原链表长度）。而对于每个循环，则维护一个 head1，按照 subLength 的长度遍历链表进行截取（获取 head2 开始的结点之后就可以进行切断），同理也切出 head2，然后就可以调用合并两个有序链表的函数对这两个链表进行合并，然后再重新连接到原链表中。这样每两个子链表切割出来后排序再连接到原链表中，完成一次循环。完成所有的循环后完成归并排序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| class Solution {
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* preHead = new ListNode(0);
ListNode* prev = preHead;
while (l1 != nullptr && l2 != nullptr) {
if (l1->val < l2->val) {
prev->next = l1;
l1 = l1->next;
} else {
prev->next = l2;
l2 = l2->next;
}
prev = prev->next;
}
prev->next = l1 == nullptr ? l2 : l1;
return preHead->next;
}
public:
ListNode* sortList(ListNode* head) {
if(head == nullptr) return nullptr;
int length = 0;
ListNode *p = head;
while(p != nullptr){
p = p->next;
length++;
}
ListNode* preHead = new ListNode(0, head);
for(int subLength = 1; subLength < length; subLength <<= 1){
ListNode *pre = preHead, *now = preHead->next;
while(now != nullptr){
ListNode *head1 = now;
for(int i = 1; i < subLength && now->next != nullptr; i++){
now = now->next;
}
ListNode *head2 = now->next;
now->next = nullptr;
now = head2;
for(int i = 1; i < subLength && now != nullptr && now->next != nullptr; i++){
now = now->next;
}
ListNode *next = nullptr;
if(now != nullptr){
next = now->next;
now->next = nullptr;
}
pre->next = mergeTwoLists(head1, head2);
while(pre->next != nullptr){
pre = pre->next;
}
now = next;
}
}
return preHead->next;
}
};
|
时间复杂度：$O(n\log n)$，其中 $n$ 是链表的长度。我们对链表进行了归并排序，需要进行 $O(\log n)$ 次归并，每次归并的时间复杂度是 $O(n)$。
空间复杂度：$O(1)$。我们只需要常数的空间存放若干变量。