# [C++] 26ms Q based non-recurrsion beat 92%

• Here is what we want to do:

list1, list2, list 3, list 4............. list k
\      /         \    /
list1'         list2' .....
\              /
list 1'' .....

Quite obvious, we are doing a reverse "tree by level traverse". With help of a queue, we can achieve O(nlgk) easily. The queue initially contains all input lists. We dequeue 2 lists every time, merge them then put the result back until the queue contains only one list which is the result.

Please note the 2 checks in mergeTwoLists() function. They reduce run time by 50%.

26ms. Beat 91.75%.

BTW, doing "erase()" etc. operations against "lists" parameter is a bad idea:

1. You should not alter the content of the parameter if not specifically instructed.
2. erase() is a O(n) operation for a vector.
``````class Solution {
public:
ListNode *mergeKLists(vector<ListNode *> &lists) {
if (lists.size() == 0) {
return NULL;
}

queue<ListNode *> q;
for (auto n : lists) {
q.push(n);
}

while (q.size() > 1) {
ListNode *l1 = q.front();
q.pop();
ListNode *l2 = q.front();
q.pop();
q.push(mergeTwoLists(l1, l2));
}

return q.front();
}

// TL;DR
private:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if (list1 == NULL) {
return list2;
}
else if (list2 == NULL) {
return list1;
}

ListNode dummy(0);
ListNode* current = &dummy;

while (list1 != NULL && list2 != NULL) {
if (list1->val <= list2->val) {
current->next = list1;
list1 = list1->next;
}
else {
current->next = list2;
list2 = list2->next;
}

current = current->next;
}

if (list1 != NULL) {
current->next = list1;
}

if (list2 != NULL) {
current->next = list2;
}

return dummy.next;
}
};
``````

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