[LeetCode Road] Merge k Sorted Lists - Solution/C++

23. Merge k Sorted Lists

Question:

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.

Example:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
 1->4->5,
 1->3->4,
 2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Input: lists = []
Output: []

Input: lists = [[]]
Output: []

Constraints:

k == lists.length

0 <= k <= 10⁴

0 <= lists[i].length <= 500

-10⁴ <= lists[i][j] <= 10⁴

lists[i] is sorted in ascending order.

The sum of lists[i].length won't exceed 10^4.

Source code

Version 1/u>

Idea:
The strategy combines with Merge Two Sorted Lists algorithm.

First, get the size of vector n because the pair of Listnodes is necessary before calling mergeTwoLists.

At 19 line, the range of for-loop is in half, we get the left Listnode lists[i] and the right Listnode lists[n - 1 - i]to do merger.

After calling mergeTwoLists, n reduces by half until n <= 1.
Why n is equal to (n + 1) / 2? Because the length is odd, one remaining ListNode can not to do merger, so it must to be counted.

Time complexity: O(log(n)*(l1 + l2))
Space complexity: O(1)

/**
 * 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.empty()) return {};
        int n = lists.size();
        
        while(n > 1) // pairs processing
        {
            for(int i = 0; i < n/2; i++)
            {
                lists[i] = mergeTwoLists(lists[i], lists[n - 1 - i]);
            }
            n = (n + 1) / 2; // Shorten vector's size
        }
        return lists.front();
    }
private:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2){
        if(!l1){
            return l2;
        }else if(!l2){
            return l1;
        }
        
        if(l1->val < l2->val){
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        }else{
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

Verion 2

Idea:
On the another hand, it can be solved by the Priority Queue.

First, the default heap of priority queue is max-heap. However, we want to get the result in ascending order, so we should implement min-heap.

/**
 * 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 {
struct compare{
    bool operator()(const ListNode* l, const ListNode* r){
        return (l->val > r->val);
    }
};
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode dummy(0);
        ListNode* tail = &dummy;
        
        priority_queue<ListNode*, vector<ListNode*>, compare> pq;
        
        for(ListNode* l: lists){
            if(l) pq.push(l);
        }
        
        while(!pq.empty()){
            tail->next  = pq.top();
            pq.pop();
            tail = tail->next;
            if(tail->next) pq.push(tail->next);
        }
        return dummy.next;
    }
};