https://leetcode.com/problems/sort-list/description/

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

Input: 4->2->1->3

Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0

Output: -1->0->3->4->5


常见排序方法有很多,插入排序,选择排序,堆排序,快速排序,冒泡排序,归并排序,桶排序等等。。它们的时间复杂度不尽相同,而这里题目限定了时间必须为O(nlgn),符合要求只有快速排序,归并排序,堆排序,代码如下:

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
class Solution {
public:
ListNode* sortList(ListNode* head) {
if(!head || !head->next)
return head;
ListNode * slow = head;
ListNode * fast = head;
ListNode * pre = head;
while(fast && fast->next) {
pre = slow;
slow = slow->next;
fast = fast->next->next;
} // slow points to the middle position
pre->next = NULL;
return mergeTwoLists(sortList(head), sortList(slow));//recursive calling
}

/* merge two sorted lists: l1 and l2 */
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode * l3 = new ListNode(-1); // create a new node
ListNode * p = l3; // use to traverse

if(l1 == NULL) return l2;
if(l2 == NULL) return l1;
if(l1 == NULL && l2 == NULL) return NULL;

while(l1 && l2) {
if( l1->val >= l2->val){ // add smaller node into l3
p->next = l2;
p = l2; // move to the newest node in l3
l2 = l2->next;
}
else {
p->next = l1;
p = l1;
l1 = l1->next;
}
if(!l1) p ->next = l2;
if(!l2) p ->next = l1;
}
return l3->next;
}
};

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

ListNode* listQuickSort(ListNode *head, ListNode *end){
if(head != end){
ListNode* newL = quickSort(head);
listQuickSort(head, newL);
listQuickSort(newL->next, end);
}
}

ListNode * quickSort(ListNode * head){
ListNode* slow = head;
ListNode* fast = head->next;
while (fast){ // the first one is the pivot
if(fast->val < head->val){
slow = slow->next;
int tem = slow->val;
slow->val = fast->val;
fast->val = tem;
}
fast = fast->next;
}
int tem = slow->val;
slow->val = head->val;
head->val = tem;
return slow; // the mid position
}
};