-
Notifications
You must be signed in to change notification settings - Fork 0
/
sort-List.cpp
54 lines (49 loc) · 1.46 KB
/
sort-List.cpp
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
//Sort a linked list in O(n log n) time using constant space complexity.
/*
考点:
1. 快慢指针;2. 归并排序。
此题经典,需要消化吸收。
复杂度分析:
T(n) 拆分 n/2, 归并 n/2 ,一共是n/2 + n/2 = n
/ \ 以下依此类推:
T(n/2) T(n/2) 一共是 n/2*2 = n
/ \ / \
T(n/4) ........... 一共是 n/4*4 = n
一共有logn层,故复杂度是 O(nlogn)
*/
class Solution{
public:
ListNode *sortList(ListNode *head){
if(!head || !head->next) return head;
ListNode* p = head, *q = head->next;
while (q && q->next)
{
p = p->next;
q = q->next->next;
}
ListNode* left = sortList(p->next);
p->next = NULL;
ListNode* right = sortList(head);
return merge(left, right);
}
ListNode* nerge(ListNode* left, ListNode* right){
ListNode dummy(0);
ListNode* p = &dummy;
while (left && right)
{
if (left->val < right->val)
{
p->next = left;
left = left->next;
}else
{
p->next = right;
right = right->next;
}
p = p->next;
}
if (left) p->next = left;
if (right) p->next = right;
return dummy.next;
}
};