cztchoice
1/21/2014 - 2:54 PM

## Merge k Sorted Lists This Solution is not time efficient, the best time complexity is o(n*logk), this one is o(n * k) http://oj.leetcode.c

Merge k Sorted Lists This Solution is not time efficient, the best time complexity is o(n*logk), this one is o(n * k) http://oj.leetcode.com/problems/merge-k-sorted-lists/

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool isEmpty(const vector<ListNode *> &lists){
for(int i = 0; i < lists.size(); i++){
if(lists[i]){
return false;
}
}
}
ListNode *mergeKLists(vector<ListNode *> &lists) {
if(lists.size() == 0){
return NULL;
}
ListNode *head = NULL;
bool set_head = false;

ListNode *it;
int min_i = 0;
int min_val = 0;
int i = 0;
while(true){
bool set_min = false;
for(int i = 0; i < lists.size(); i++){
if(lists[i]){
if(!set_min){
min_i = i;
min_val = lists[i]->val;
set_min = true;
}
else{
if(lists[i]->val < min_val){
min_i = i;
min_val = lists[i]->val;
}
}
}
}
if(!set_min){
break;
}
ListNode *temp = lists[min_i];
lists[min_i] = lists[min_i]->next;