Difficulty: Hard
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
Hide Tags
Show Similar Problems
---------------------------------------------
To merge K sorted linked lists, similar like the procedure in later part of merge sort:
including
1). merge two sorted lists;
2). divide K lists into small lists until 1 or 2 lists in order to use 1) (Divide and Conquer); here backtracking is used.
NOTE: If only use 1), e.g., merge 1 and 2 lists then merge 3......until the last one, this way will exceed the time constrain.
NOTE**: subList1.assign(it, it + subList.size() / 2);//assign not include the last one: [first,last)
assign doesn't include the last!!
//////////////////////////////////////////////////////////////////
//
class Solution {
public:
//merge two lists
ListNode* mergeList(ListNode*a, ListNode*b){
ListNode* dum = new ListNode(-1), *tmp = dum;
//check
input
if (a == NULL)return b;
if (b == NULL)return a;
//merge
two lists
while (a != NULL || b != NULL){
if (a == NULL){
tmp->next = b;
break;
}
else if (b == NULL){
tmp->next = a;
break;
}
else if (a->val<b->val){
tmp->next = a;
a = a->next;
tmp = tmp->next;
}
else{
tmp->next = b;
b = b->next;
tmp = tmp->next;
}
}
tmp = dum->next;
delete dum;
return tmp;
}
//backtracking to devide K lists into small untill two or
one list
ListNode* mergeBackTrac(vector<ListNode*> subList){
ListNode* tmp = NULL, *tmp1 = NULL, *tmp2 = NULL;
if (subList.size() == 0)return tmp;
else if (subList.size() == 1){
tmp = mergeList(subList[0], tmp);
}
else if (subList.size() == 2){
tmp = mergeList(subList[0], subList[1]);
}
else{
std::vector<ListNode*>::iterator it = subList.begin();
vector<ListNode*> subList1;
subList1.assign(it, it + subList.size() / 2);//assign not include the last one: [first,last)
vector<ListNode*> subList2;
subList2.assign(it + subList.size() / 2, subList.end());
tmp1 = mergeBackTrac(subList1);
tmp2 = mergeBackTrac(subList2);
tmp = tmp = mergeList(tmp1, tmp2);
}
return tmp;
}
//main function
ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode* dP = NULL;
dP = mergeBackTrac(lists);
return dP;
}
};
No comments:
Post a Comment