分析
- 计算链表长度
- 自底向上归并排序
- 按步长
i 从小到大逐步归并，初始步长为 1，逐渐乘以 2，直到覆盖整个链表
- 每次归并时，将链表分成两部分，每部分包含
i 个节点，然后对这两部分进行归并
- 最后将归并的结果重新连接到链表中
- 归并两个子链表
- 使用两个指针分别指向两个子链表的头部，逐一比较节点的值，将较小值的节点加入到排序后的链表中，直到处理完两部分中的所有节点
- 更新链表
时间复杂度
每轮归并的时间复杂度为 O(n)，需要进行 log(n) 轮归并，因此总复杂度为 O(nlogn)
空间复杂度
采用自底向上归并，不需要额外空间，空间复杂度为 O(1)
C++代码
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
|
class Solution
{
public:
ListNode* sortList(ListNode* head)
{
// 第 1 步：计算链表长度
int n = 0;
for (ListNode* p = head; p; p = p->next)
++n;
// 第 2 步：归并排序
for (int i = 1; i < n; i *= 2)
{
ListNode* dummy = new ListNode(-1); // 虚拟头节点
ListNode* cur = dummy;
for (int j = 1; j <= n; j += i * 2)
{
// 划分两段链表
ListNode *p = head, *q = p;
for (int k = 0; k < i && q; ++k)
q = q->next; // 第二段起点
ListNode* o = q;
for (int k = 0; k < i && o; ++k)
o = o->next; // 下一部分的起点
// 归并两段链表
int l = 0, r = 0;
while (l < i && r < i && p && q)
{
if (p->val <= q->val)
{
cur->next = p;
p = p->next;
++l;
}
else
{
cur->next = q;
q = q->next;
++r;
}
cur = cur->next;
}
// 剩余部分处理
while (l < i && p)
{
cur = cur->next = p;
p = p->next;
++l;
}
while (r < i && q)
{
cur = cur->next = q;
q = q->next;
++r;
}
// 更新链表头
head = o;
}
cur->next = nullptr;
head = dummy->next; // 更新链表头为新的排序结果
}
return head;
}
};
|
