插入排序 O(n^2)
利用vector來進行插入排序，這裡展示了較标準的插入排序
leetcode執行16ms的執行個體
1.從連結清單中的第二個節點和第一個節點比，如果小于，就得插入到連結清單頭，這裡可以建立啞頭部來簡化操作
2.從連結清單中把要插入的節點取出後，從啞頭部周遊該插入的位置（由于需要知道待插入位置的前驅，就必須從啞頭部開始，并判别其後繼的值）
ListNode* insertionSortList(ListNode* head) {
if(head == nullptr) return nullptr;
int len = 0;
ListNode* last = head; //判斷第二個節點與其前驅值的大小，我們必須知道其前驅
ListNode* dummy = new ListNode(0); //建立啞頭部，用于便利處理插入頭部的情況
dummy->next = head;
while(last->next){
if(last->next->val >= last->val){ //後一個比較大，不必排序 必須用第二個元素和前一個比較
last = last->next;
}else{
//為了應對插入的可能是頭部，需要從啞頭部開始
ListNode* cur = dummy;
while(cur->next->val < last->next->val) cur = cur->next;
//去除需要插入的節點
ListNode* aim = last->next;
last->next = aim->next;
//插入新位置
aim->next = cur->next;
cur->next = aim;
}
}
return dummy->next;
} 歸并排序 O(nlgn)
對數組做歸并排序的空間複雜度為 O(n)，分别由新開辟數組O(n)和遞歸函數調用O(logn)組成，而根據連結清單特性：數組額外空間：連結清單可以通過修改引用來更改節點順序，無需像數組一樣開辟額外空間；遞歸額外空間：遞歸調用函數将帶來O(logn)O(logn)的空間複雜度，是以若希望達到O(1)O(1)空間複雜度，則不能使用遞歸。
通過遞歸實作連結清單歸并排序，有以下兩個環節：
- 分割 cut 環節： 找到目前連結清單中點，并從中點将連結清單斷開（以便在下次遞歸 cut 時，連結清單片段擁有正确邊界）；我們使用 fast,slow 快慢雙指針法，奇數個節點找到中點，偶數個節點找到中心左邊的節點。找到中點 slow 後，執行 slow.next = None 将連結清單切斷。遞歸分割時，輸入目前連結清單左端點 head 和中心節點 slow 的下一個節點 tmp(因為連結清單是從 slow 切斷的)。cut 遞歸終止條件： 當head.next == None時，說明隻有一個節點了，直接傳回此節點。
- 合并 merge 環節： 将兩個排序連結清單合并，轉化為一個排序連結清單。雙指針法合并，建立輔助ListNode h 作為頭部。設定兩指針 left, right 分别指向兩連結清單頭部，比較兩指針處節點值大小，由小到大加入合并連結清單頭部，指針交替前進，直至添加完兩個連結清單。傳回輔助ListNode h 作為頭部的下個節點 h.next。時間複雜度 O(l + r)，l, r 分别代表兩個連結清單長度。
- 截止條件：當題目輸入的 head == None 時，直接傳回None。
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode fast = head.next, slow = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode tmp = slow.next;
slow.next = null;
ListNode left = sortList(head);
ListNode right = sortList(tmp);
ListNode h = new ListNode(0);
ListNode res = h;
while (left != null && right != null) {
if (left.val < right.val) {
h.next = left;
left = left.next;
} else {
h.next = right;
right = right.next;
}
h = h.next;
}
h.next = left != null ? left : right;
return res.next;
}
} ListNode* sortList(ListNode* head) {
//截止條件：head為零或者head隻有一個節點
if(head == nullptr || head->next == nullptr) return head;
//拆分
//偶數個節點，slow指向中點右側，奇數個節點，slow指向中間節點的下一個節點
//ListNode* fast = head;
//ListNode* slow = head;
//while(fast){
//fast = fast->next;
//slow = slow->next;
//if(fast == nullptr) break;
//fast = fast->next;
//}
//這裡需要的是偶數個節點，slow指向中點左側，奇數個節點，slow指向中間節點，可以友善斷鍊
ListNode* fast = head->next;
ListNode* slow = head;
while(fast != nullptr && fast->next != nullptr){
slow = slow->next;
fast = fast->next->next;
}
ListNode* tmp = slow->next;
slow->next = nullptr;
ListNode* left = sortList(head);
ListNode* right = sortList(tmp);
//合并 外排 利用啞頭部
ListNode dummyhead(0);
ListNode* dummytail = &dummyhead;
while(left != nullptr && right != nullptr){
if(left->val < right->val){
dummytail->next = left;
left = left->next;
}else{
dummytail->next = right;
right = right->next;
}
dummytail = dummytail->next;
}
dummytail->next = (left == nullptr ? right : left);
return dummyhead.next;
} - 對于非遞歸的歸并排序，需要使用疊代的方式替換cut環節：我們知道，cut環節本質上是通過二分法得到連結清單最小節點單元，再通過多輪合并得到排序結果。
- 每一輪合并merge操作針對的單元都有固定長度intv，例如：第一輪合并時intv = 1，即将整個連結清單切分為多個長度為1的單元，并按順序兩兩排序合并，合并完成的已排序單元長度為2。第二輪合并時intv = 2，即将整個連結清單切分為多個長度為2的單元，并按順序兩兩排序合并，合并完成已排序單元長度為4。以此類推，直到單元長度intv >= 連結清單長度，代表已經排序完成。
- 根據以上推論，我們可以僅根據intv計算每個單元邊界，并完成連結清單的每輪排序合并，例如:當intv = 1時，将連結清單第1和第2節點排序合并，第3和第4節點排序合并，……當intv = 2時，将連結清單第1-2和第3-4節點排序合并，第5-6和第7-8節點排序合并，……。當intv = 4時，将連結清單第1-4和第5-8節點排序合并，第9-12和第13-16節點排序合并，……。
- 算法流程，模拟上述的多輪排序合并：
- 統計連結清單長度length，用于通過判斷intv < length判定是否完成排序；
- 額外聲明一個節點res，作為頭部後面接整個連結清單，用于：intv *= 2即切換到下一輪合并時，可通過res.next找到連結清單頭部h；執行排序合并時，需要一個輔助節點作為頭部，而res則作為連結清單頭部排序合并時的輔助頭部pre；後面的合并排序可以将上次合并排序的尾部tail用做輔助節點。
- 在每輪intv下的合并流程：根據intv找到合并單元1和單元2的頭部h1, h2。由于連結清單長度可能不是2^n，需要考慮邊界條件：在找h2過程中，如果連結清單剩餘元素個數少于intv，則無需合并環節，直接break，執行下一輪合并；若h2存在，但以h2為頭部的剩餘元素個數少于intv，也執行合并環節，h2單元的長度為c2 = intv - i。合并長度為c1, c2的h1, h2連結清單，其中：合并完後，需要修改新的合并單元的尾部pre指針指向下一個合并單元頭部h。（在尋找h1, h2環節中，h指針已經被移動到下一個單元頭部）。合并單元尾部同時也作為下次合并的輔助頭部pre。當h == None，代表此輪intv合并完成，跳出。
- 每輪合并完成後将單元長度×2，切換到下輪合并：intv *= 2。
ListNode* cut(ListNode* head, int n){
ListNode* ptr = head;
while(--n && ptr){
ptr = ptr->next;
}
if(!ptr) return nullptr; //如果數量不足以劃分，就傳回nullptr
ListNode* next = ptr->next; //p是指向前連結清單的尾節點
ptr->next = nullptr;
return next;
}
//利用啞頭節點進行外排
ListNode* merge(ListNode* l1, ListNode* l2){
ListNode dummyHead(0);
ListNode* dummyTail = &dummyHead;
while(l1&&l2){
if(l1->val < l2->val){
dummyTail->next = l1;
l1 = l1->next;
}else{
dummyTail->next = l2;
l2 = l2->next;
}
dummyTail=dummyTail->next;
}
dummyTail->next = (l1 == nullptr ? l2 : l1);
return dummyHead.next;
}
ListNode* sortList(ListNode* head) {
//非遞歸方式
//使用啞頭部
ListNode dummyHead(0);
dummyHead.next = head;
//統計連結清單長度
ListNode* ptr = head;
int length = 0;
while(ptr){
length++;
ptr = ptr->next;
}
for(int intv = 1; intv < length; intv <<= 1){
ListNode* cur = dummyHead.next;
ListNode* tail = &dummyHead;
while(cur){
ListNode* left = cur;
ListNode* right = cut(left,intv); //left->@ right->@->@->@->@...
cur = cut(right,intv); //left->@ right->@ cur->@->@->@...
tail->next = merge(left,right);
while(tail->next){
tail = tail->next;
}
}
}
return dummyHead.next;
}