leetcode-排序链表

点击:题目链接:给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。
进阶:
你可以在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序吗?

思路

自定向下,使用快慢指针,不断分治链表然后两两合并。

代码

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
class Solution {
public:
ListNode* sortList(ListNode* head) {
return sort(head, nullptr);
}

ListNode* sort(ListNode* head, ListNode* tail) {
if (head == nullptr) return nullptr;

if (head->next == tail) {
//若只有两个节点,将其分开
head->next = nullptr;
return head;
}

ListNode* low = head;
ListNode* fast = head;

if (fast->next) fast = fast->next->next;

while (fast!= tail) {
low = low->next;
fast = fast->next;

if (fast!= tail) {
fast = fast->next;
}
}
ListNode* mid = low->next;
return merge(sort(head, mid), sort(mid, tail));
}


ListNode* merge(ListNode* node1, ListNode* node2) {
ListNode* head = new ListNode(0);
ListNode* cur = head;

while (node1 && node2) {
ListNode* temp;
if (node1->val < node2->val) {
temp = node1->next;
cur->next = node1;

cur = node1;
node1 = temp;
}
else{
temp = node2->next;
cur->next = node2;

cur = node2;
node2 = temp;
}
}

if (!node1) {
cur->next = node2;
}
else if (!node2) {
cur->next = node1;
}

return head->next;
}
};

复杂度

时间:O(NlogN), 空间:O(logN)

思路二(拓展)

自底向上。 直接两两节点不断比较,再两两合并。

主要注意点一个是择出所需链表节点个数,另一个是在向上合并时要注意成2倍递增

代码

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
/**
* 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) {
ListNode* dummyhead = new ListNode(0);
dummyhead->next = head;

ListNode* tmplen = head;
int len = 0;
while (head) {
++len;
head = head->next;
}

for (int i = 1; i < len; i<<= 1) {
ListNode* cur = dummyhead->next;
ListNode* tail = dummyhead;

while (cur) {
ListNode* left = cur;
ListNode* right = cut(left, i);
cur = cut(right, i);

ListNode* p = merge(left, right);

tail->next = p;

while (tail->next) {
tail = tail->next;
}
}
}
return dummyhead->next;

}

ListNode* cut(ListNode* head, int n) {
ListNode* p = head;

if (n == 0) return p;

while (p) {
--n;
if (n > 0) {
p = p->next;
}
else {
break;
}
}

if (p == nullptr) return nullptr;

ListNode* tmp = p->next;
p->next = nullptr;

return tmp;
}

ListNode* merge(ListNode* l1, ListNode* l2) {
ListNode* dummyh = new ListNode(0);
ListNode* cur = dummyh;

while (l1 && l2) {
if (l1->val < l2->val) {
cur->next = l1;
cur = l1;
l1 = l1->next;
}
else {
cur->next = l2;
cur = l2;
l2 = l2->next;
}
}

cur->next = l1 ? l1 : l2;

return dummyh->next;
}
};

复杂度

时间:O(NlogN), 空间:O(1)

作者

Dylan Zhu

发布于

2021-04-17

更新于

2021-04-17

许可协议

评论

:D 一言句子获取中...

加载中,最新评论有1分钟缓存...