LeetCode 148. 【归并排序】排序链表
原题链接
中等
作者:
大明湖的鱼
,
2021-01-14 19:15:54
,
所有人可见
,
阅读 346
思路
- 本题要求时间复杂度为$O(nlogn)$ 空间复杂度为$O(1)$
- merge(l1,l2) 传统归并的空间复杂度为$O(n)$
- cut(l1,n) 返回的切掉从l1开始数n个节点以后,后半部分链的头结点
- 先两两归并,再4个为一组归并,不断倍增组内元素的size
- bottom-to-up
- 本代码要烂熟于心
代码
/**
* 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:
//要求时间复杂度Onlogn 空间复杂度O1
ListNode* sortList(ListNode* head) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
auto p = head;
int length = 0;
while(p){
length++;
p = p->next;
}
for(int size = 1 ;size < length ; size <<= 1){
auto cur = dummy->next;
auto tail = dummy;
while(cur){
auto left = cur;
auto right = cut(left,size);
cur = cut(right,size);
tail->next = merge(left,right);
while(tail->next) tail = tail->next;
}
}
return dummy->next;
}
ListNode* cut(ListNode* head , int n){
auto p = head;
while(--n && p){
p = p->next;
}
if(!p) return nullptr;
auto next = p->next;
p->next = nullptr;
return next;
}
ListNode* merge(ListNode* l1,ListNode* l2){
ListNode* dummy = new ListNode(0);
auto p = dummy;
while(l1 && l2){
if(l1->val < l2->val){
p->next = l1;
p = l1;
l1 = l1->next;
}
else {
p->next = l2;
p = l2;
l2 = l2->next;
}
}
p->next = l1 ? l1 : l2;
return dummy->next;
}
};