# Time complexity O(n). C++ code without recursive and Priority-Queue

• By creating an extra node with val equaling INT_MAX，we can do it within O(sum(length of every list)) time complexity and O(lists.size())

``````	ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.size() == 0) return NULL;
for (int i = 0; i < lists.size(); ++i) {
if (!lists[i])
{
lists[i] = new ListNode(INT_MAX);
}
else {
ListNode *pt = lists[i];
while (pt->next) pt = pt->next;
pt->next = new ListNode(INT_MAX);
}
}

vector<ListNode*> pts(lists);
ListNode preHead = ListNode(INT_MIN);
ListNode *cur = &preHead;
while (true) {
int min = INT_MAX;
int minLoc = -1;
for (int i = 0; i < pts.size(); ++i) {
if (pts[i]->val <= min) {
min = pts[i]->val;
minLoc = i;
}
}

if (!pts[minLoc]->next) {
cur->next = NULL;
break;
}
cur->next = pts[minLoc];
cur = cur->next;
pts[minLoc] = pts[minLoc]->next;
}

return preHead.next;
}
``````

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