I use the method below to solve this problem:

I set a loop. In every loop, I try to find out the smallest head node in k lists, then I move this node to the list which would be returned as the result.

here is my code:

ListNode* mergeKLists(vector<ListNode*>& lists) {

ListNode* res = NULL;

ListNode* head = NULL;

while (1){

bool flag = false;

int minIndex;

int minValue = 0x7fffffff;

for (int i = 0; i < lists.size(); i++) {

if (lists[i]) flag = true;

else continue;

if (lists[i]->val < minValue) {

minIndex = i;

minValue = lists[i]->val;

}

}

if (flag) {

if (!res) {

res = head = lists[minIndex];

lists[minIndex] = lists[minIndex]->next;

continue;

}

res->next = lists[minIndex];

res = res->next;

lists[minIndex] = lists[minIndex]->next;

continue;

}

break;

}

return head;

}

Cause this method takes k*n times to compare，does that means its time complexity is kn ?

I'm really confused why this method turns out to be very Inefficient. Its run time is 538ms. :(

Hope somebody can help explain this problem.

Thank you !!