题目链接：Sort List
Sort a linked list in O(n log n) time using constant space complexity.
这道题的要求是对链表进行排序，要求时间复杂度O(nlogn)，并且常量空间复杂度。
排序，时间复杂度要求O(nlogn)，因此需要考虑分治思路的排序：归并排序或者快排。
归并排序的空间复杂度为O(nlogn)，貌似不太合适。不过，由于是对链表进行排序，无需申请空间存储，因此每次调用的时候无需申请空间，因此空间复杂度可以达到O(1)（递归开销姑且不算，或者直接迭代进行归并）。
至于快排，需要从两端往中间进行划分，因此不是十分适合单链表，不过应该仍可以实现。而且快排的最差情况是O(n2)，所有这里暂时不考虑。
接下来说说归并排序吧：
- 首先，需要找到中点，这可以利用快慢指针f和s进行查找。其中f每次走2步，s每次走1步，直到f到达链表尾，此时s刚好走到链表中间；
- 接下来，需要在中间部分切开，切记，一定要切割开，否则左边链表无法判别结束。同时记录左边链表为l，右边链表为r；
- 最后对l和r分布递归调用排序函数，并对其进行合并。至于递归终止条件就是传入链表为NULL或者只有1个节点。
时间复杂度：O(nlogn)
空间复杂度：O(1)（递归开销姑且不算）
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
class Solution
{
public:
ListNode *sortList(ListNode *head)
{
if(head == NULL || head -> next == NULL)
return head;
ListNode *f = head -> next, *s = head;
while(f != NULL && f -> next != NULL)
{
f = f -> next -> next;
s = s -> next;
}
ListNode *l = head, *r = s -> next;
s -> next = NULL;
return mergeTwoLists(sortList(l), sortList(r));
}
private:
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
{
ListNode *h = new ListNode(0), *p;
for(p = h; l1 != NULL && l2 != NULL; p = p -> next)
{
if(l1 -> val < l2 -> val)
p -> next = l1, l1 = l1 -> next;
else
p -> next = l2, l2 = l2 -> next;
}
p -> next = l1 != NULL ? l1 : l2;
return h -> next;
}
};
接下来，也可以非递归进行实现：
时间复杂度：O(nlogn)
空间复杂度：O(1)
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
class Solution
{
public:
ListNode *sortList(ListNode *head)
{
if(head == NULL || head -> next == NULL)
return head;
ListNode *carry, *counter[64];
int fill = 0;
while(head != NULL)
{
// 取链表首节点，同时head后移一步
carry = head;
head = head -> next;
carry -> next = NULL;
int i = 0;
while(i < fill && counter[i] != NULL)
{
carry = mergeTwoLists(counter[i], carry);
counter[i ++] = NULL;
}
swap(carry, counter[i]);
if(i == fill)
++ fill;
}
for(int i = 1; i < fill; ++ i)
counter[i] = mergeTwoLists(counter[i], counter[i - 1]);
return counter[fill - 1];
}
private:
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
{
ListNode *h = new ListNode(0), *p;
for(p = h; l1 != NULL && l2 != NULL; p = p -> next)
{
if(l1 -> val < l2 -> val)
p -> next = l1, l1 = l1 -> next;
else
p -> next = l2, l2 = l2 -> next;
}
p -> next = l1 != NULL ? l1 : l2;
return h -> next;
}
};
For example:
list is 1 -> 3 -> 5 -> 7 -> 2 -> 4 -> 6 -> 8 -> NULL
1.
get 1, and list is 3 -> 5 -> 7 -> 2 -> 4 -> 6 -> 8 -> NULL
- counter[0]: 1 -> NULL
- counter[1]: NULL
fill = 1
2.
get 3, and list is 5 -> 7 -> 2 -> 4 -> 6 -> 8 -> NULL
- counter[0]: NULL
- counter[1]: 1 -> 3 -> NULL
- counter[2]: NULL
fill = 2
3.
get 5, and list is 7 -> 2 -> 4 -> 6 -> 8 -> NULL
- counter[0]: 5 -> NULL
- counter[1]: 1 -> 3 -> NULL
- counter[2]: NULL
fill = 1
4.
get 7, and list is 2 -> 4 -> 6 -> 8 -> NULL
- counter[0]: NULL
- counter[1]: NULL
- counter[2]: 1 -> 3 -> 5 -> 7 -> NULL
- counter[3]: NULL
fill = 3
5.
get 2, and list is 4 -> 6 -> 8 -> NULL
- counter[0]: 2 -> NULL
- counter[1]: NULL
- counter[2]: 1 -> 3 -> 5 -> 7 -> NULL
- counter[3]: NULL
fill = 3
6.
get 4, and list is 6 -> 8 -> NULL
- counter[0]: NULL
- counter[1]: 2 -> 4 -> NULL
- counter[2]: 1 -> 3 -> 5 -> 7 -> NULL
- counter[3]: NULL
fill = 3
7.
get 6, and list is 8 -> NULL
- counter[0]: 6 -> NULL
- counter[1]: 2 -> 4 -> NULL
- counter[2]: 1 -> 3 -> 5 -> 7 -> NULL
- counter[3]: NULL
fill = 3
8.
get 8, and list is NULL.
- counter[0]: NULL
- counter[1]: NULL
- counter[2]: NULL
- counter[3]: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> NULL
- counter[4]: NULL
fill = 4
then return counter[fill - 1].