Posted on

## Submission 1

Special Testcase: [[]]

```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if(lists.size() == 0) return nullptr;

ListNode* res = nullptr;
ListNode* ptr = res;

int count = 0;
vector<ListNode*> ptrs;
for(int i = 0; i < lists.size(); ++i) {
ptrs.push_back(lists[i]);
if(lists[i] != nullptr) count++;
}

for(;count > 0;) {
int minimum = numeric_limits<int>::max();
int index = -1;
for(int i = 0; i < lists.size(); ++i) {
if(ptrs[i] != nullptr) {
if(ptrs[i]->val < minimum) {
minimum = ptrs[i]->val;
index = i;
}
}
}
if(res == nullptr) {
res = new ListNode(minimum);
ptr = res;
} else {
ptr->next = new ListNode(minimum);
ptr = ptr->next;
}
ptrs[index] = ptrs[index]->next;
if(ptrs[index] == nullptr) count--;
}
return res;
}
};```

## Submission 2

Maintaining an increasing list of the first elements, no improvement but only space cost added.

```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
list<pair<ListNode*, int>> minList;

for(int i = 0; i < lists.size(); ++i) {
if(lists[i] == nullptr) continue;
if(minList.empty()) minList.push_back(make_pair(lists[i], i));
else {
auto p = minList.begin();
for(; p != minList.end() && p->first->val < lists[i]->val; advance(p, 1));
if(p == minList.end())
minList.push_back(make_pair(lists[i], i));
else
minList.insert(p, make_pair(lists[i], i));
}
lists[i] = lists[i]->next;
}

ListNode* res = nullptr;
for(ListNode* p = res; !minList.empty(); ) {
if(res == nullptr) {
res = new ListNode(minList.begin()->first->val);
p = res;
} else {
p->next = new ListNode(minList.begin()->first->val);
p = p->next;
}

int index = minList.begin()->second;
ListNode* list = lists[index];
minList.erase(minList.begin());
if(list != nullptr) {
auto q = minList.begin();
for(; q != minList.end() && q->first->val < list->val; advance(q, 1));
if(q == minList.end())
minList.push_back(make_pair(list, index));
else
minList.insert(q, make_pair(list, index));
lists[index] = lists[index]->next;
}

}

return res;
}
};```

## Submission 3

Using a priority queue

```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
auto cmp = [](ListNode*& node1, ListNode*& node2){return node1->val > node2->val;};
priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
for(auto list : lists) {
if(list != nullptr) {
pq.push(list);
}
}

ListNode* res = nullptr;

for(ListNode* p = res; !pq.empty(); ) {
auto minimum = pq.top();
pq.pop();
if(res == nullptr) {
res = new ListNode(minimum->val);
p = res;
} else {
p->next = new ListNode(minimum->val);
p = p->next;
}
if(minimum->next != nullptr) {
pq.push(minimum->next);
}
}

return res;
}
};```