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:
//链表的排序：归并排序
//1.找到中间节点
//2.将链表分为两部分
//3.实现有序链表的排序
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;
}
//此时slow所在的位置就是中间节点所在的位置，prev指向slow的前一个节点
//我们人为的让链表从slow这个地方断开，head->prev是链表的前半段，slow到完是链表的右半部分
prev->next=nullptr;
//递归在左、右两端继续找中间节点
ListNode*l=MergSort(head);
ListNode*r=MergSort(slow);
//当分割的不能分割时，进行排序，最开始两两排序，到后来四四排序
return Sort(l,r);
}
ListNode* sortList(ListNode* head) {
//1.判断节点是否为空
if(head==nullptr)
return head;
//2.进入归并排序，寻找中间节点
return MergSort(head);
}
};