題目鏈接
tag:
- Hard;
- Divide and Conquer;
question
??Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Example:
Input:
[
1->4->5,
1->3->4,
2->6
]
Output: 1->1->2->3->4->4->5->6
思路：
??這道題讓我們合并k個(gè)有序鏈表，最終合并出來的結(jié)果也必須是有序的胆绊，之前有道 Merge Two Sorted Lists氨鹏，是混合插入兩個(gè)有序鏈表。這道題增加了難度压状，變成合并k個(gè)有序鏈表了仆抵，但是不管合并幾個(gè)，基本還是要兩兩合并种冬。那么我們首先考慮的方法是能不能利用之前那道題的解法來解答此題镣丑。答案是肯定的，但是需要修改娱两，怎么修改呢莺匠，最先想到的就是兩兩合并，就是前兩個(gè)先合并十兢，合并好了再跟第三個(gè)趣竣，然后第四個(gè)直到第k個(gè)。這樣的思路是對(duì)的旱物，但是效率不高遥缕，沒法通過OJ，所以我們只能換一種思路宵呛，這里就需要用到分治法 Divide and Conquer Approach单匣。簡(jiǎn)單來說就是不停的對(duì)半劃分，比如k個(gè)鏈表先劃分為合并兩個(gè)k/2個(gè)鏈表的任務(wù)，再不停的往下劃分户秤，直到劃分成只有一個(gè)或兩個(gè)鏈表的任務(wù)码秉，開始合并。舉個(gè)例子來說比如合并6個(gè)鏈表鸡号，那么按照分治法转砖，我們首先分別合并0和3，1和4鲸伴，2和5堪藐。這樣下一次只需合并3個(gè)鏈表，我們?cè)俸喜?和3挑围，最后和2合并就可以了。代碼中的k是通過 (n+1)/2 計(jì)算的糖荒，這里為啥要加1呢杉辙，這是為了當(dāng)n為奇數(shù)的時(shí)候，k能始終從后半段開始捶朵，比如當(dāng)n=5時(shí)蜘矢，那么此時(shí)k=3，則0和3合并综看，1和4合并品腹，最中間的2空出來。當(dāng)n是偶數(shù)的時(shí)候红碑，加1也不會(huì)有影響舞吭，比如當(dāng)n=4時(shí)，此時(shí)k=2析珊，那么0和2合并羡鸥，1和3合并，完美解決問題忠寻，參見代碼如下：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.empty()) return NULL;
int n = lists.size();
while (n > 1) {
int k = (n + 1) / 2;
for (int i=0; i<n/2; ++i)
lists[i] = mergeTwoLists(lists[i], lists[i+k]);
n = k;
}
return lists[0];
}
// 合并兩個(gè)鏈表
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode *dummy = new ListNode(-1), *cur = dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
cur->next = l1;
l1 = l1->next;
}
else {
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
if (l1) cur->next = l1;
if (l2) cur->next = l2;
return dummy->next;
}
};
相似題目：
