题目描述
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
题解
- ListNode merge(ListNode h1, ListNode* h2) 双路归并
- ListNode cut(ListNode h, int n) 断链
- dummy Head
常数级空间复杂度，不能使用递归，使用bottom-to-up的算法。先两个两个的 merge，完成一趟后，再 4 个4个的 merge，直到结束。
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
| ListNode* merge(ListNode* h1, ListNode* h2)
{
ListNode dummy(0);
ListNode* p = &dummy;
while (h1&&h2)
{
if (h1->val > h2->val)
{
p->next = h2;
h2 = h2->next;
p = p->next;
}
else
{
p->next = h1;
h1 = h1->next;
p = p->next;
}
}
p->next = h1 ? h1 : h2;
return dummy.next;
}
ListNode* cut(ListNode* h, int n)
{
ListNode* p = h;
while (--n&&p)
p = p->next;
if (!p)return nullptr;
ListNode* nh = p->next;
p->next = nullptr;
return nh;
}
ListNode* sortList(ListNode* head) {
ListNode dummyHead(0);
dummyHead.next = head;
ListNode *current = dummyHead.next;
ListNode *tail = &dummyHead;
int length = 0;
ListNode*tmp = head;
while (tmp)
{
tmp = tmp->next;
length++;
}
ListNode *left, *right;
for (int step = 1; step < length; step<<1)
{
current = dummyHead.next;
tail = &dummyHead;
while (current)
{
left = current;
right = cut(current, step);
current = cut(right, step);
tail->next = merge(left, right);
while (tail->next)
{
tail = tail->next;
}
}
}
return dummyHead.next;
}
|
或许可以恢复状态了。