連結清單排序是各大廠面試官經常會問到的一個面試題，這個題目很好的将排序和連結清單操作結合在一起，有較高的區分度，如果你在面試中被問到了這個問題，你該怎樣解決呢？在往下看前先仔細想一想。
簡單思路
相信很多同學都對數組排序比較熟悉，冒泡、堆排、快排等等簡直手到擒來，但當被問到要用連結清單來排序時很多同學是一臉懵逼的，表示從來沒想過連結清單還要排序，這才是真正考驗你對排序了解深度的時刻，如果你真的徹底了解了排序，那麼這個問題簡直不要太簡單，但僅僅浮于表面含糊其辭的話是通不過後續寫代碼環節的。
很多同學都能答上來用冒泡和插排來實作，這當然是可以的，但是時間複雜度O(n2)，顯然這不是面試官想要的答案。
再被進一步問能不能加快排序速度時，有的同學反應過來可以把連結清單中的值放到數組中，然後就可以用常見的排序方法進行排序了，比如快排；這種方法也可以，這樣時間複雜度來到了O(nlogn)，但是由于需要額外借助數組，是以空間複雜度是O(n)，那麼能不能進一步優化呢？
優化思路一：歸并排序
實際上是可以的，讓我們來思考一下歸并排序這種思想，歸并排序是說我們把數組分為兩半，左邊一半排序然後右邊一半排序，最後合并兩個有序數組，那麼這種思路能不能應用在連結清單排序中呢？實際上也是可以的。
假設我們有一個連結清單：
首先我們将其分為兩半：
這樣我就得到了兩段連結清單，然後我們分别對其進行排序，由于每段連結清單隻有兩個元素了，是以排序就很簡單了，這樣我們就得到了兩個有序的連結清單：
最後将這兩段連結清單合并起來：
這樣我們就得到了一個有序的連結清單。
是以我們可以看到歸并實際上有兩個過程，第一個是自上而下的拆分：
第二個是自下而上的排序與合并：
這就是歸并排序的思想，怎麼樣很簡單吧。
有了這樣的分析，代碼就很簡單了，具體的實作如下：
ListNode* merge_list(ListNode* l1, ListNode* l2){ ListNode h(0); ListNode* p = &h; while(l1&&l2){ if(l1->val<=l2->val){ p->next=l1; l1=l1->next; } else { p->next=l2; l2=l2->next; } p=p->next; } p->next=l1?l1:l2; return h.next; } ListNode* sortList(ListNode* head) { if (head==NULL||head->next==NULL) return head; ListNode h(0); h.next=head; ListNode* s=&h; ListNode* f=&h; while(f&&f->next){ f=f->next->next; s=s->next; } ListNode* r=s->next; s->next=NULL; return merge_list(sortList(head), sortList(r)); }
優化思路二：快速排序
對于O(nlogn)排序算法怎麼能忘了快速排序呢？有的同學可能會有疑問，連結清單也可以用快排嗎？答案是可以的。
首先讓我來想一想快排的實作思想：
- 找到數組中任意一個元素(可能有的資料有不同的選取政策)
- 然後根據該元素将整個數組劃分為兩段，小于該元素的一半以及大于該元素的一半，然後将小于該元素的一半放到左邊，把大于該元素的一半放到右邊，把該元素放到中間，這樣該元素就放到了最終位置上
- 對左邊一半和右邊一半重複上述過程
用到連結清單上呢？其實是一樣的，我們以該連結清單為例：
假設我們用連結清單第一個節點進行劃分，從該示例中可以看到，節點2和1比節點3小，是以可以放到一個連結清單中；節點4比節點3大，可以放到另一個連結清單中，這樣我們得到了兩個連結清單。
然後把“比節點3小”的這一段連結清單到節點3的左邊，把“比節點3大”的這一段連結清單放到節點3的右邊，這樣我們就得到了：
從這裡可以看到節點3已經被放到了最終位置，也就是排好序後應該所處的位置，然後我們在左邊和右邊的連結清單上重複上述過程，這樣整個連結清單就排好序啦！
怎麼樣，是不是也很簡單。
具體實作代碼如下：
pair<ListNode*,ListNode*> quick_sort(ListNode* list) { if (list == NULL || list->next == NULL) return pair<ListNode*,ListNode*>(list, list); ListNode A(0); ListNode B(0); ListNode* pa = &A; ListNode* pb = &B; ListNode* mid = list; list = list->next; while(list) { ListNode* t = list->next; if(list->val < mid->val) { pa->next = list; pa = pa->next; } else { pb->next = list; pb = pb->next; } list = t; } pa->next = NULL; pb->next = NULL; mid->next = NULL; pair<ListNode*,ListNode*> L = list_quick_sort(A.next); pair<ListNode*,ListNode*> R = list_quick_sort(B.next); if (L.first == NULL) { mid->next = R.first; return pair<ListNode*,ListNode*>(mid, R.second); } else if (R.first == NULL) { L.second->next = mid; return pair<ListNode*,ListNode*>(L.first, mid); } else { L.second->next = mid; mid->next = R.first; return pair<ListNode*,ListNode*>(L.first, R.second); } } ListNode* sortList(ListNode* L) { if (L == NULL || L->next == NULL) return L; return quick_sort(L).first; }
總結
說起排序很多同學都知道歸并和排序，但卻并不知道該怎樣用這兩種算法包含的思想來解決問題，其實這說明了很有可能對其了解的不徹底，在這裡我們詳解講解了兩種排序思想在連結清單上的應用，希望能加深大家的了解。
更多精彩内容，歡迎關注公衆号“碼農的荒島求生”。