Merge k sorted linked lists and return it as
one sorted list. Analyze and describe its complexity.
Subscribe to see which companies asked this
question
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
private:
ListNode * merge_help(vector<ListNode*>&lists,int l,int r){
if(l>=r)
return lists[l];
int mid=(l+r)/2;
ListNode * left =merge_help(lists,l,mid);
ListNode * right=merge_help(lists,mid+1,r);
ListNode * temp =new ListNode (-1);
ListNode *cur =temp;
while(left&&right){
if(left->val<=right->val){
cur->next =left;
left=left->next;
}
else{
cur->next=right;
right=right->next;
}
cur=cur->next;
}
if(left)
cur->next=left;
if(right)
cur->next=right;
return temp->next;
}
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if(lists.size()==0)
return NULL;
return merge_help(lists,0,lists.size()-1);
}
};