Sort List

原題鏈接Sort List

要求在O(nlogn)的時間復雜度下排序鏈表，且時間復雜度在O(1)

涉及到O(logn)的算法有

• 二分法
• 快速排序
• 歸并排序

二分法通常應用在已排序的序列中，且常用語查找算法，而不用作排序算法

快速排序需要從兩邊向中間逼近，對待鏈表而言同樣不現實

歸并排序類似于二分，不斷切分已有序列再合并成一個有序序列，排序操作集中在合并過程中且通常是將兩個有序序列合并成一個

綜上，歸并排序是適用于對鏈表的排序算法，算法流程如下

找到當前鏈表的中點，可以通過walker,runner指針的方法定位鏈表中部位置

將已有鏈表分成左右兩部分分別作為獨立的鏈表繼續切分，直到鏈表只有一個節點或為nullptr時返回

在返回的過程中將左右兩部分（有序）合并成一個有序鏈表，繼續向上返回

最后得到排序后的鏈表

代碼如下：

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/ class Solution { public:ListNode* sortList(ListNode* head) {if(head == nullptr || head->next == nullptr)return head;/* 找到鏈表中間的節點，prev代表中間節點的前一個節點 */ListNode* walker = head;ListNode* runner = head;ListNode* prev = nullptr;while(runner && runner->next){prev = walker;walker = walker->next;runner = runner->next->next;}prev->next = nullptr;/* 此時head被分成兩部分，head->prev->nullptr是一個，walker->nullptr是一個 *//* 對左右兩部分分別進行切分和排序　*/ListNode* lhs = sortList(head);ListNode* rhs = sortList(walker);/*　返回的lhs和rhs是已經排好序的鏈表，接下來將這兩個有序鏈表合并成一個 */return mergeSort(lhs, rhs);} private:/* 歸并排序，將兩個有序鏈表合并成一個　*/ListNode* mergeSort(ListNode* lhs, ListNode* rhs){ListNode* header = new ListNode(-1);ListNode* cur = header;while(lhs || rhs){ListNode* next = nullptr;if(lhs == nullptr){next = rhs;rhs = rhs->next;}else if(rhs == nullptr){next = lhs;lhs = lhs->next;}else if(lhs->val > rhs->val){next = rhs;rhs = rhs->next;}else{next = lhs;lhs = lhs->next;}next->next = nullptr;cur->next = next;cur = next;}cur = header->next;delete header;return cur;} };

---

Sort Colors

原題鏈接Sort Colors

給定一個數組，數組中的元素只有0,1,2三種，對數組進行排序，要求不能使用標準庫的排序函數

數組中只有0,1,2三種數值，那么遍歷一遍記錄這三個數分別有多少，最后一次賦值即可（低配版的計數排序）

代碼如下：

class Solution { public:void sortColors(vector<int>& nums) {vector<int> counts(3, 0);for(int n : nums)++counts[n];int n = 0;for(int i = 0; i < 3; ++i){for(int j = 0; j < counts[i]; ++j)nums[n++] = i;}} };

---

上述兩道題都是排序算法的類型，歸并排序的時間復雜度是O(nlogn)，并且適用于鏈表。而計數排序不是基于比較的排序算法，復雜度是O(k),k是待排序序列中元素的個數。

總結

以上是生活随笔為你收集整理的每天一道LeetCode-----链表排序，要求复杂度在O(nlogn)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。