Description

Submission 1

Special Testcase: [[]]

/**
 * Definition for singly-linked list.
 * 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.

/**
 * Definition for singly-linked list.
 * 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

/**
 * Definition for singly-linked list.
 * 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;
    }
};