# Share my ugly C++ solution in 44ms

• 1. Check the heads of all lists, find the minimum value

2. If more than one lists have the head with the minimum value, merge all minimum nodes to the first list

3. After one loop, append all minimum value nodes to the result

4. Goto next loop until all lists reach tail nodes

``````ListNode* mergeKLists(vector<ListNode*>& lists) {
int count = lists.size();
if (0 == count) return NULL;
if (1 == count) return lists[0];
ListNode* p = NULL;
ListNode* cur = NULL;
while (true) {
int k = -1;
int min_val = 0x7FFFFFFF;
for (int i = 0; i < count; ++i) {
// list reach tail
if (!lists[i]) continue;
if (lists[i]->val < min_val) {
// find smaller value, k = i
min_val = lists[i]->val;
k = i;
} else if (lists[i]->val == min_val) {
if (k >= 0) {
// find the same minimum value
// insert the head node of lists[i] to lists[k]
// then move lists[i] to next
// e.g.
//     lists[k] = [1,3,5,7,9], lists[i] = [1,1,4,5,7]
// =>  lists[k] = [1,1,1,3,5,7,9], lists[i] = [4,5,7]
while (lists[i] && lists[i]->val == min_val) {
ListNode* next = lists[i]->next;
lists[i]->next = lists[k]->next;
lists[k]->next = lists[i];
lists[i] = next;
}
} else {
// lists[0].val == 0x7FFFFFFF
k = i;
}
}
}
if (k >= 0) {
// if k >= 0, find next node, else all lists reach tail
if (cur) {
cur->next = lists[k];
cur = lists[k];
lists[k] == lists[k]->next;
} else {
cur = lists[k];
p = lists[k];
lists[k] == lists[k]->next;
}
while (lists[k] && lists[k]->val == min_val) {
cur = lists[k];
lists[k] = lists[k]->next;
}
} else {
// all lists reach tail
break;
}
}
return p;
}``````

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