### leetcode Question 52: Merge k Sorted Lists

Merge Sorted Array
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Analysis:
While the lists is not empty, keep merging the list to the result list. Method to merge two lists is the same as Question 54

Code(updated 201309):
/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *mergeKLists(vector<ListNode *> &lists) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (lists.size()==0){return NULL;}
ListNode *p;
ListNode *q;
for (int i=1;i<lists.size();i++){
q = lists[i];
while (q){
if (!p->next){
p->next = q;
break;
}
if (p->next->val<q->val){
p=p->next;
}else{
ListNode *l = p->next;
p->next = q;
q=q->next;
p->next->next = l;
p=p->next;
}
}
}
}
};


Code(old version):

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* merg2(ListNode* l1, ListNode* l2){
if (l1==NULL){
}
while (l1!=NULL && l2!=NULL){
if (l1->val < l2->val){
if (l1->next != NULL){
prev = l1;
l1=l1->next;
}else{
l1->next = l2;
break;
}
}else{
ListNode* tmp = l2->next;
prev->next = l2;
l2->next = l1;
prev = l2;
l2 = tmp;
}
}
}
ListNode *mergeKLists(vector<ListNode *> &lists) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (lists.empty()){return NULL;}
lists.pop_back();
while (!lists.empty()){
lists.pop_back();
}
}