LeetCode 148 排序链表
🟠 中等偏上 https://leetcode.cn/problems/sort-list/description/
插入排序
最容易想到的 插入排序。
start为每次遍历位置的前一个，从 fake_head开始。 cur为遍历指针，从start 开始。 min时最小值的前一个。
找到后将min后面的节点插入到start 后面。
/**
* Definition for singly-linked list.
* 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) {
//插入排序
ListNode* fake_head = new ListNode();
fake_head->next = head;
ListNode* start = fake_head; //插入到start 后面.
while(start->next){
ListNode* cur = start;//每次遍历位置的前面一个
ListNode* min = start;//记录最小值前面一个.
while(cur->next){
if(cur->next->val<min->next->val){
min = cur;
}
cur = cur->next;
}
// cout<<min->next->val<<endl;
ListNode* min_item = min->next;
min->next = min->next->next;
min_item->next = start->next;
start->next = min_item;
start = start->next;
}
return fake_head->next;
}
};
归并排序
https://leetcode.cn/problems/sort-list/description/comments/3747
merge_sort ：对 head 开始的链表进行排序。 merge：对l 和 r 进行合并。
/**
* Definition for singly-linked list.
* 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* merge_sort(ListNode* head){
if(!head||head->next==nullptr) return head;
ListNode* slow = head;
ListNode* fast = head;
ListNode* pre = nullptr;
while(fast&&fast->next){
pre = slow;
slow = slow->next;
fast = fast->next->next;
}
pre->next = nullptr;
ListNode* l = merge_sort(head);
ListNode* r = merge_sort(slow);
return merge(l,r);
}
ListNode* merge(ListNode* l,ListNode* r){
ListNode* fake_head = new ListNode();
ListNode* cur = fake_head;
while(l&&r){
if(l->val<r->val){
cur->next = l;
cur = cur->next;
l = l->next;
}else{
cur->next = r;
cur = cur->next;
r = r->next;
}
}
if(l){
cur->next = l;
}
if(r){
cur->next= r;
}
return fake_head->next;
}
ListNode* sortList(ListNode* head) {
return merge_sort(head);
}
};