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);
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/299339.html
標籤：其他
上一篇：??思維導圖整理大廠面試高頻陣列: 兩萬字詳解各種陣列求和(建議收藏)??
下一篇：??Kettle--老板說：這套生產資料庫千萬、億級資料量遷移方案，學會就賺了??(作業學習必備，建議收藏)