LeetCode SortList 单向链表排序问题

原题传送门: https://leetcode.com/problems/sort-list/

如题,需要在O(nlogn)时间复杂度常量空间的条件下实现对单向链表的排序。

首先,要在O(nlogn)时间复杂度下完成排序,需要用到归并排序或堆排序(快排在最坏情况下复杂度仍为O(n^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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
ListNode* merge(ListNode *p1, ListNode* p2) {
ListNode *head = new ListNode(0), *p = (!p1 && !p2) ? NULL : head;
while (p1 && p2) {
if (p1->val < p2->val) {
p->next = p1;
p1 = p1->next;
} else {
p->next = p2;
p2 = p2->next;
}
p = p->next;
}
while (p1) {
p->next = p1;
p1 = p1->next;
p = p->next;
}
while (p2) {
p->next = p2;
p2 = p2->next;
p = p->next;
}
return head->next;
}
ListNode* sort(ListNode* &head, int len) {
ListNode *realHead = head;
if (len == 1) {
ListNode *tmp = head;
head = head->next;
tmp->next = NULL;
} else {
realHead = merge(sort(head, len/2), sort(head, len-len/2));
}
return realHead;
}
public:
ListNode* sortList(ListNode* head) {
if (head == NULL) return NULL;
int len = 0;
ListNode *p = head;
while (p) {
len++;
p = p->next;
}
return sort(head, len);
}
};

以上方法可以说是非常巧妙,不过从严格意义上来说,递归的深度也是对一种存储空间的消耗(函数递归是用压栈实现的),所以该方法不能满足使用常量空间的要求。
还是使用归并排序,但是这次需要用非递归的算法,不是特别的困难,具体见以下代码:

方法二(非递归)

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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
ListNode* merge(ListNode *p1, ListNode* p2, int t, ListNode* &tail) {
ListNode *head = new ListNode(0), *p = (!p1 && !p2) ? NULL : head;
int t1 = t, t2 = t;
while (p1 && t1 && p2 && t2) {
if (p1->val < p2->val) {
p->next = p1;
p1 = p1->next;
t1--;
}
else {
p->next = p2;
p2 = p2->next;
t2--;
}
p = p->next;
}
while (p1 && t1) {
p->next = p1;
p1 = p1->next;
t1--;
p = p->next;
}
while (p2 && t2) {
p->next = p2;
p2 = p2->next;
t2--;
p = p->next;
}
tail = p;
return head->next;
}
public:
ListNode* sortList(ListNode* head) {
int len = 0;
ListNode *p = head;
while (p) {
len++;
p = p->next;
}
for (int t = 1; t <= len; t <<= 1) {
ListNode *p1, *p2, *tail, *last, *res;
p = head;
last = NULL;
while (p || last) {
p1 = p2 = p;
int i = t;
while (p2 && i--) p2 = p2->next;
p = p2; i = t;
while (p && i--) p = p->next;
res = merge(p1, p2, t, tail);
if (last == NULL) head = res;
else last->next = res;
last = tail;
}
}
return head;
}
};

需要注意的就是此时由于归并的两个链表是有长度限制的,所以需要做一些改动。