Code & Fun

今天中午在Lintcode上刷了一道题——链表排序

题目很短:

在 O(n log n) 时间复杂度和常数级的空间复杂度下给链表排序。

最近几天也在做排序算法的实验,所以看到这道题想刷一下。

从题目的要求我们可以大概的想出几种能达到要求的排序:

  • 快速排序
  • 归并排序

这里是归并排序的实现:

归并排序的大概思路是:

在待排序列中找到中间元素,将待排序列分成两个待排序列,分别对这两个待排序列递归地调用归并排序,当待排序列中元素只剩一个时,序列显然有序。

现在只需要将两个有序序列合并成一个有序序列。


实现:

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
class ListNode {
public:
int val;
ListNode* next;
ListNode(int v):val(v),next(nullptr){}
}

ListNode * sortList(ListNode * head) {
// write your code here
if (!head || !head->next) return head;


ListNode *fast,*slow;
fast = slow = head;
while(fast->next != nullptr && fast->next->next != nullptr) {
fast = fast->next->next;
slow = slow->next;
}
fast = slow;
slow = slow->next;
fast->next = nullptr;
fast = sortList(head);
slow = sortList(slow);
return mergeList(fast,slow);

}

ListNode *mergeList(ListNode *l1,ListNode *l2){
if (!l1) return l2;
else if (!l2) return l1;

ListNode* ret = new ListNode(0);
ListNode*p = ret;
while(l1 && l2) {
if (l1->val > l2->val) {
ret->next = l2;
ret = ret->next;
l2 = l2->next;
} else {
ret->next = l1;
ret = ret->next;
l1 = l1->next;
}
}
ret->next = (l1)?l1:l2;
ret = p->next;
delete p;
return ret;
}

这里的难点就是找出中间元素,将一个序列分成两个序列,这里的实现是快慢指针来实现的,即:

1
2
3
4
5
6
ListNode *fast,*slow;
fast = slow = head;
while(fast->next != nullptr && fast->next->next != nullptr) {
fast = fast->next->next;
slow = slow->next;
}

本文首发于Code & Fun