# 32 ms C++ solution

• In order to make it faster, do it a divide-and-conquer way: merge ListNodes pairwise and you will have n/2 ListNodes, then merge them again pairwise and you will have n/4 ListNodes, and so on...

``````/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.size() == 0) {
return NULL;
}
if (lists.size() == 1) {
return lists.at(0);
}
vector<ListNode*> newlists;
while (lists.size() > 1) {
newlists.clear();
for (int i = 0; i < lists.size() / 2; i ++) {
ListNode* result = mergeTwo(lists.at(2 * i), lists.at(2 * i + 1));
newlists.push_back(result);
}
if (lists.size() > 2 * (lists.size() / 2)) {
newlists.push_back(lists.at(lists.size() - 1));
}
lists = newlists;
//cout << lists.size() << " size of the lists" << endl;
}
return newlists.at(0);
}

ListNode* mergeTwo(ListNode* a, ListNode* b) {
ListNode* merged = NULL;
if (a == NULL and b == NULL) {
return merged;
}
else if (a == NULL and b != NULL) {
merged = b;
}
else if (a != NULL and b == NULL) {
merged = a;
}
else {
ListNode* current1 = a;
ListNode* current2 = b;
merged = new ListNode(0);
ListNode* current = merged;
while (current1 != NULL or current2 != NULL) {
if (current1 == NULL and current2 != NULL) {
current->next = current2;
current = current->next;
current2 = current2->next;
}
else if (current1 != NULL and current2 == NULL) {
current->next = current1;
current = current->next;
current1 = current1->next;
}
else {
if (current1->val < current2->val) {
current->next = current1;
current = current->next;
current1 = current1->next;
}
else {
current->next = current2;
current = current->next;
current2 = current2->next;
}
}
//cout << "current val " << current->val << endl;
}
merged = merged->next;
}
return merged;
}
};
``````

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