Leetcode 23 Solution

Leetcode Question Link

https://leetcode.com/problems/merge-k-sorted-lists

Thinking Process

The most straightforward solution is to compare the current head of each list and find the smallest one to connect to the result list. If there are M lists, and each list has an average length of N. The time complexity will be O(M * N).

If we were to think about the algorithm, there is one thing that we can improve, which is to grab the smallest element from the current list heads. Finding a smallest element reminds of us min-heap. We can keep all the list head values in the min-heap, and then selecting the smallest element from it only costs O(lg M) time. The overall time complexity will be O(N * lg M).

There is one implementation details to note. In this implementation, we’ll have to keep the current list head, and the list itself, and the corresponding list index at the same time. Whenever we grab an element from the heap, we’ll need to find out the list, and push its next value. Luckily, we can use a trick here, which is to put them into a tuple. Since sorting a tuple is based on the first value first, it’s basically sorting it based on the list head value.

Time & Space Complexity

Assuming there are M lists, and each list has an average length of N

• Time complexity: O(N * lg M)
• Space complexity: O(M * N)

Solution

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode dummyNode(0);
        ListNode* head = &dummyNode;
        ListNode* p = head;
        priority_queue<pair<int, ListNode*>, std::vector<pair<int, ListNode*>>, std::greater<pair<int, ListNode*>>> q;

        for (auto list : lists)
            if (list)
                q.push(make_pair(list->val, list));

        while (q.empty() == false)
        {
            auto pair = q.top();
            int value = pair.first;
            auto node = pair.second;
            q.pop();

            p->next = new ListNode(value);
            p = p->next;

            if (node->next)
                q.push(make_pair(node->next->val, node->next));
        }

        return head->next;
    }
};