023 Merge k Sorted Lists[H]

1 題目描述

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

難度：Hard

2 題目樣例

無。

3 題意分析

排序K個有序的鏈表。

總體上說來，和之前的Merge Two Sorted Lists類似。

但是鏈表的數量由2攀升至K，難度確實是增加了許多。（直觀感受）

在《演算法導論》一書堆排序的課後題目中，有相同的題目。

4 思路分析

首先要明確這樣一點......由於此題和之前的Merge Two Sorted Lists的相似性，完全可以把之前的Merge Two Sorted Lists中的操作寫成函數，進行再利用。

（我之前沒有寫成函數形式，感覺血虧。）

1.暴力法：

這是毫無思維難度的一種方法......我在寫代碼之前甚至不能確定這種方法能不能通過。

無腦的把1，2合併，然後把1，2合併的結果再和3合併，1，2，3合併的結果再和4合併......以此類推。

我們可以計算一下這個過程的時間複雜度，假設每個鏈表的平均元素個數為n，合併1，2鏈表的時候，要遍歷2n個頂點，合併1，2，3鏈表的時候，要遍歷3n個頂點......以此類推。

最後需要遍歷的元素總個數是2n+3n+...+kn，轉化為等差級數求和，可得最後的時間複雜度為 。

代碼實現如下：

class Solution{ public: ListNode* mergeKLists(vector<ListNode*>& lists) { if(lists.size() == 0) return NULL; ListNode*res = lists[0]; for(int i = 1; i < lists.size(); i++) res = merge2list(res, lists[i]); return res; } ListNode *merge2list(ListNode *head1, ListNode*head2) { ListNode node(0), *res = &node; while(head1 && head2) { if(head1->val <= head2->val) { res->next = head1; head1 = head1->next; } else { res->next = head2; head2 = head2->next; } res = res->next; } if(head1) res->next = head1; else if(head2) res->next = head2; return node.next; }};

交了一發，居然通過了。但是效率確實是排在後邊。

2.分治法：

利用分治的思想，把合併k個鏈表的任務轉化為兩個合併k/2個鏈表的任務，四個合併 k/4個鏈表的任務......直到每次合併的鏈表只剩下1個為止。

代碼實現如下：

class Solution { public: ListNode *mergeKLists(vector<ListNode *> &lists) { int n = lists.size(); if(n == 0)return NULL; while(n >1) { int k = (n+1)/2; for(int i = 0; i < n/2; i++) lists[i] = merge2list(lists[i], lists[i + k]); n = k; } return lists[0]; } ListNode *merge2list(ListNode *head1, ListNode*head2) { ListNode node(0), *res = &node; while(head1 && head2) { if(head1->val <= head2->val) { res->next = head1; head1 = head1->next; } else { res->next = head2; head2 = head2->next; } res = res->next; } if(head1) res->next = head1; else if(head2) res->next = head2; return node.next; } };

這次的時間複雜度還是比較令人滿意的。

3.利用優先隊列：

因為這個題目出現在《演算法導論》的堆排序一章，我們可以考慮一下這題目到底和堆排序有什麼關係。

我只要維護一個k個大小的最小堆，初始化堆中的元素為鏈表的頭節點，每次從堆中選擇最小的元素加入到要返回的鏈表，並且把加入到返回鏈表中的節點所在鏈表的下一個節點加入到堆中。當堆為空時，所有的節點就都被加入到結果鏈表中了。

至於堆的實現，我們可以使用優先隊列。

代碼實現如下：

class Solution {public: struct cmp { bool operator ()(const ListNode *a, const ListNode *b) { return a->val > b->val; } }; ListNode *mergeKLists(vector<ListNode *> &lists) { int n = lists.size(); if(n == 0)return NULL; ListNode node(0), *res = &node; priority_queue<ListNode*, vector<ListNode*>, cmp> que; for(int i = 0; i < n; i++) if(lists[i]) que.push(lists[i]); while(!que.empty()) { ListNode * p = que.top(); que.pop(); res->next = p; res = p; if(p->next) que.push(p->next); } return node.next; }};

5 後記

《演算法導論》真是一本好書啊！雖然我期末考完試之後就再也沒看過了（逃