# Is there any solution whose time complexity is kn?

• 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;
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) {
lists[minIndex] = lists[minIndex]->next;
continue;
}
res->next = lists[minIndex];
res = res->next;
lists[minIndex] = lists[minIndex]->next;
continue;
}
break;
}
}

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 !!

• Sorry, the code is as below:

``````ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode* res = 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) {
lists[minIndex] = lists[minIndex]->next;
continue;
}
res->next = lists[minIndex];
res = res->next;
lists[minIndex] = lists[minIndex]->next;
continue;
}
break;
}
}``````

• O(kn) is slow enough :) the optimal would be O(nLog k )

• @aygul Thank you, aygul.
Could you tell me how to solve this problem in just O(nlogk)? :)

• @angiehoo see my latest topic in the problem discussion.

• @aygul great! thank you!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.