描述
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
思路
借鉴Merge Two Sorted Lists的解决思路，对两个数组先进行排序，然后两两组合，排成一个序列。
将此视为一种迭代的分而治之的解决方案。
mergeTwoLists方法是一种递归的合并两个序列的方法
注意：
尽量不用erase方法，太耗时。
一些优化以避免vector.erase()
比如下述：
while(lists.size() > ){
lists.push_back(mergeTwoLists(lists[], lists[]));
lists.erase(lists.begin());
lists.erase(lists.begin());
}
return lists.front();
改为使用指针方法遍历vector，最后取vector.back()
最终解决方案：
/**
* 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 nullptr;
}
if(lists.size() == ) return lists[];
int i = ;
while(i < lists.size() - ){
lists.push_back(mergeTwoLists(lists[i], lists[i+]));
i += ;
}
return lists.back();
} ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(l1 == nullptr){
return l2;
}
if(l2 == nullptr){
return l1;
}
if(l1->val <= l2->val){
l1->next = mergeTwoLists(l1->next, l2);
return l1;
}
else{
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
};