给你链表的头结点 head ，请将其按 升序
排列并返回 排序后的链表 。
示例
输入：head = [4,2,1,3]
输出：[1,2,3,4]
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
输入：head = []
输出：[]
思路：归并排序
把链表从中间节点分成两个链表，然后递归下去，直到都为空。
那么我们如何找到中间节点呢？只需要通过快慢指针即可，慢指针每次走一步，快指针走两步，这样快指针走向空时，慢指针指向的就是中间节点。
1
2
3
4
| while(fast != nullptr && fast->next != nullptr){
slow = slow->next;
fast = fast->next->next;
}
|
对于分割递归的base case：
当
head == nullptr时，直接返回nullptr（对应链表没有元素）
当head->next == nullptr时，直接返回head（链表只有一个元素，无法再分）
合并阶段：
- 当两个链表都不为空时，我们把小的元素添加到新的链表上
- 当
list1不为空，list2为空时，直接把链表插到开头
- 当
list2不为空，list1为空时，直接把链表插到开头
综上代码如下：
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
| #include <bits/stdc++.h>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
ListNode* sortList(ListNode* head) {
if(head == nullptr) return nullptr;
if(head->next == nullptr) return head;
return sort_list(head, nullptr);
}
ListNode* sort_list(ListNode* head, ListNode* tail){
if (head == nullptr) {
return head;
}
if (head->next == tail) {
head->next = nullptr;
return head;
}
ListNode* slow = head, *fast = head;
while(fast != tail && fast->next != tail){
slow = slow->next;
fast = fast->next->next;
}
ListNode* mid = slow;
return merge(sort_list(head, mid), sort_list(mid, tail));
}
ListNode* merge(ListNode* list1, ListNode* list2){
ListNode* dummy = new ListNode(0);
ListNode* temp = dummy, *temp1 = list1, *temp2 = list2;
while(temp1 != nullptr && temp2 != nullptr){
if(temp1->val <= temp2->val){
temp->next = temp1;
temp1 = temp1->next;
}else{
temp->next = temp2;
temp2 = temp2->next;
}
temp = temp->next;
}
if(temp1 != nullptr){
temp->next = temp1;
}else if(temp2 != nullptr){
temp->next = temp2;
}
return dummy->next;
}
};
ListNode* construct(vector<int>& v){
ListNode* node = new ListNode(-1);
ListNode* head = node;
for(int i = 0; i < v.size(); i++){
ListNode* temp = new ListNode(v[i]);
head->next = temp;
head = head->next;
}
return node->next;
}
int main(){
vector<int> v = {4, 2, 1 ,3};
ListNode* head = construct(v);
Solution a;
ListNode* res = a.sortList(head);
ListNode* cur = res;
while(cur != nullptr){
cout << cur->val << "->";
cur = cur->next;
}
cout << endl;
return 0;
}
|