8000 added 122. Sort List · binEncoder/LeetCode@74aa11a · GitHub
[go: up one dir, main page]

Skip to content

Commit 74aa11a

Browse files
committed
added 122. Sort List
1 parent 9fa6438 commit 74aa11a

File tree

3 files changed

+141
-0
lines changed

3 files changed

+141
-0
lines changed

122. Sort List/README.md

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
链表的排序,需要掌握的至少有两种。
2+
3+
1. 插入排序 - 只在面试的时候使用
4+
2. 归并排序 - 最基础的"合理"排序
5+
6+
我知道插入排序会比较搞笑,但还是先用插入排序试了一试,果然 TimeOut 了。感兴趣的童鞋可以来看看我在 [弹指神通之链表排序](http://segmentfault.com/blog/pezy/1190000002490878#articleHeader6) 中的方法。
7+
8+
于是我改用了另一个基础的方案,归并排序。AC 后发现效果并不差的离谱,是 C++ 方案中的头筹呢。
9+
10+
-----
11+
12+
简单说说归并排序。
13+
14+
关键在于**归并**,这是废话。但想要归并,显然就要有两段链表,我们的原始链表显然就应该分割为两段。我们把这个分割过程,抽取成一个函数。
15+
16+
```cpp
17+
void frontBackSplit(ListNode *source, ListNode **frontRef, ListNode **backRef) {
18+
if (source == NULL || sorce->next == NULL) return;
19+
else {
20+
ListNode *slow = source, *fast = source->next;
21+
while (fast != NULL) {
22+
fast = fast->next;
23+
if (fast != NULL) {
24+
slow = slow->next;
25+
fast = fast->next;
26+
}
27+
}
28+
*frontRef = source;
29+
*backRef = slow->next;
30+
slow->next = NULL;
31+
}
32+
}
33+
```
34+
35+
这里面一个基本的技巧就是快慢指针,LeetCode 里面链表题中出现过多次使用这个技巧解决的,有心的童鞋应该会心一笑。
36+
37+
另外,我们可以利用之前的遇到过的 [019. Merge Two Sorted Lists](../019. Merge Two Sorted Lists).
38+
39+
这样我们的 `mergeSort` 函数将会无比简单。
40+
41+
```cpp
42+
void mergeSort(ListNode **headRef) {
43+
ListNode *head = *headRef, *front, *back;
44+
if (head == NULL || head->next == NULL) return;
45+
frontBackSplit(head, &front, &back);
46+
mergeSort(&front);
47+
mergeSort(&back);
48+
*headRef = sortedMerge(front, back);
49+
}
50+
```

122. Sort List/main.cpp

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
#include "solution.h"
2+
#include <iostream>
3+
#include <initializer_list>
4+
using namespace std;
5+
6+
ListNode *create_linkedlist(std::initializer_list<int> lst)
7+
{
8+
auto iter = lst.begin();
9+
ListNode *head = lst.size() ? new ListNode(*iter++) : nullptr;
10+
for (ListNode *cur=head; iter != lst.end(); cur=cur->next)
11+
cur->next = new ListNode(*iter++);
12+
return head;
13+
}
14+
15+
void clear(ListNode *head)
16+
{
17+
while (head) {
18+
ListNode *del = head;
19+
head = head->next;
20+
delete del;
21+
}
22+
}
23+
24+
void printList(ListNode *head) {
25+
for (ListNode *cur = head; cur; cur = cur->next)
26+
cout << cur->val << "->";
27+
cout << "\b\b " << endl;
28+
}
29+
30+
int main()
31+
{
32+
Solution s;
33+
ListNode *a = create_linkedlist({4,3,5,1,9});
34+
ListNode *ret = s.sortList(a);
35+
printList(ret);
36+
clear(ret);
37+
}

122. Sort List/solution.h

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
#include <cstddef>
2+
3+
struct ListNode {
4+
int val;
5+
ListNode *next;
6+
ListNode(int x) : val(x), next(NULL) {}
7+
};
8+
9+
class Solution {
10+
void moveNode(ListNode **destRef, ListNode **sourceRef) {
11+
ListNode *newNode = *sourceRef;
12+
*sourceRef = newNode->next;
13+
newNode->next = *destRef;
14+
*destRef = newNode;
15+
}
16+
ListNode *sortedMerge(ListNode *a, ListNode *b) {
17+
ListNode *ret = nullptr, **lastPtrRef = &ret;
18+
for (; a && b; lastPtrRef = &((*lastPtrRef)->next)) {
6D4E 19+
if (a->val <= b->val) moveNode(lastPtrRef, &a);
20+
else moveNode(lastPtrRef, &b);
21+
}
22+
*lastPtrRef = a ? a : b;
23+
return ret;
24+
}
25+
void frontBackSplit(ListNode *source, ListNode **frontRef, ListNode **backRef) {
26+
if (source == nullptr || source->next == nullptr) {*frontRef = source; *backRef = nullptr;}
27+
else {
28+
ListNode *slow = source, *fast = source->next;
29+
while (fast != nullptr) {
30+
fast = fast->next;
31+
if (fast != nullptr) {
32+
slow = slow->next;
33+
fast = fast->next;
34+
}
35+
}
36+
*frontRef = source;
37+
*backRef = slow->next;
38+
slow->next = nullptr;
39+
}
40+
}
41+
void mergeSort(ListNode **headRef) {
42+
ListNode *head = *headRef, *front, *back;
43+
if (head == nullptr || head->next == nullptr) return;
44+
frontBackSplit(head, &front, &back);
45+
mergeSort(&front);
46+
mergeSort(&back);
47+
*headRef = sortedMerge(front, back);
48+
}
49+
public:
50+
ListNode *sortList(ListNode *head) {
51+
mergeSort(&head);
52+
return head;
53+
}
54+
};

0 commit comments

Comments
 (0)
0