题目描述
合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
解决方案
我们采用二分法与迭代法来解决该问题,每次讲两个链表合并成一个链表后,将得到的新链表继续进行与下一个链表进行合并,具体代码如下:
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
class Solution {
public:
ListNode* mergeTwoList(ListNode* l1,ListNode* l2){
ListNode *node = new ListNode(-1);
ListNode *cur = node;
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 node->next;
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
if(lists.size() ==0){
return NULL;
}
if(lists.size()==1){
return lists[0];
}
int len = lists.size();
while(len>1){
int n = (len+1)/2;
for(int i=0;i<len/2;++i){
lists[i] = mergeTwoList(lists[i],lists[i+n]);
}
len = n;
}
return lists[0];
}
};