题目解析

在单链表上使用O(nlgn)的排序算法

方法一 快速排序

快速排序有一种partition需要从两边往里交换,这种在单链表上行不通,这里改为维持一个low指针,在它之前的节点(包括low指向的)的值都小于目标。
比如:

1
2
输入: 3->4->2->1->6
输出: 1->2->3->4->6

下图是第一次partition过程
parition

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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* sortList(ListNode* head) {
partition(head, nullptr);
return head;
}

void partition(ListNode* begin, ListNode* end) {
if (begin == end) return;
if (begin->next == end) return;
ListNode * low = begin, *p = begin;
while (p) {
if (p->val < begin->val) {
low = low->next;
swap(p->val, low->val);
}
p = p->next;
}
swap(begin->val, low->val);
partition(begin, low);
while (low->next && low->next->val == low->val) low = low->next;
partition(low->next, end);
}
};

方法二 归并排序

首先找到当前链表的中点mid,将链表分为切割成两个链表,[start,mid)[mid, end),递归调用归并排序,最后再将这两个链表合并。合并函数可以参考使用21. Merge Two Sorted Lists

归并

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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* sortList(ListNode* head) {
return mergeSort(head);
}
private:
ListNode* mergeSort(ListNode* begin) {
if (!begin || !begin->next) return begin;
ListNode* mid = findMid(begin); // 中点

ListNode * left = mergeSort(begin);
ListNode * right = mergeSort(mid);
return merge(left, right);
}
ListNode* merge(ListNode* l1, ListNode* l2) { // 合并两个链表
ListNode* head = new ListNode(-1), *p = head;
while (l1 && l2) {
if (l1->val < l2->val) {
p->next = l1;
l1 = l1->next;
} else {
p->next = l2;
l2 = l2->next;
}
p = p->next;
}
while (l1) {
p->next = l1;
l1 = l1->next;
p = p->next;
}
while (l2) {
p->next = l2;
l2 = l2->next;
p = p->next;
}
ListNode* result = head->next;
delete head;
return result;
}
ListNode* findMid(ListNode* head) { // 找到中点,中点前的节点的next变为空,这样一个链表被切开成两个单独的链表
ListNode* fast = head, *slow = head;
ListNode* prev = nullptr;
while (fast && fast->next) {
fast = fast->next->next;
prev = slow;
slow = slow->next;
}
if (prev) prev->next = nullptr;
return slow;
}
};