148. 排序链表
你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。
进阶:
你可以在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序吗?
示例 1:
输入:head = [4,2,1,3]
输出:[1,2,3,4]
示例 2:
输入:head = [-1,5,3,4,0]
输出:[-1,0,3,4,5]
示例 3:
输入:head = []
输出:[]
链表排序的最佳方法:归并排序
1.找到中间节点
2.将中间节点断成左右两半,然后再次递归找到中间节点,再次进行分割,直到最后分割成一个一个的单个元素
3.然后两两排序,之后四四排序…直到最后将整张链表排成一个有序链表
这个思想和归并排序一样,归并排序的原理也是将数据分割成小部分,然后每一个小部分进行排序,让局部有序,然后整体有序
class Solution {
public:
ListNode*Sort(ListNode*&l,ListNode*&r)
{
ListNode*dummyHead=new ListNode(0);
ListNode*cur=dummyHead;
while(l!=nullptr&&r!=nullptr)
{
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!=nullptr)
{
cur->next=l;
}
if(r!=nullptr)
{
cur->next=r;
}
return dummyHead->next;
}
ListNode*MergSort(ListNode*&head)
{
if(head->next==nullptr)
return head;
ListNode*slow=head;
ListNode*fast=head;
ListNode*prev=nullptr;
while(fast&&fast->next)
{
prev=slow;
slow=slow->next;
fast=fast->next->next;
}
prev->next=nullptr;
ListNode*l=MergSort(head);
ListNode*r=MergSort(slow);
return Sort(l,r);
}
ListNode* sortList(ListNode* head) {
if(head==nullptr)
return head;
return MergSort(head);
}
};
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)