merge_k_sorted_lists.cc

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

/*
 * O(N log k) time and O(1) space, where N is the total number of nodes.
 *
 * # Explanation of the time complexity
 *
 * Let n be an upper bound on the number of nodes of each list.
 *
 * We iteratively merge pairs of lists as follows:
 *
 * Iteration 1. Merge k/2 lists. Each merge requires O( n) + O( n) = O(2n) time.
 * Iteration 2. Merge k/4 lists. Each merge requires O(2n) + O(2n) = O(4n) time.
 * Iteration 3. Merge k/8 lists. Each merge requires O(4n) + O(4n) = O(8n) time.
 * ...
 * Iteration i. Merge k/2^i lists. Each merge requires O(2^i n) time.
 *
 * As we can merge at most \log_2 k times, the time complexity is:
 *
 * \sum_{i = 1}^{\log_2 k} (nk 2^i)/2^i = O(nk log_2 k).
 *
 * Finally, since O(nk) = O(N), then O(nk log_2 k) = O(N log_2 k) = O(N log k).
*/

class Solution {
    ListNode* mergeTwoLists(ListNode* a, ListNode* b) {
        ListNode head, * tail = &head;

        while (a && b) {
            if (a->val <= b->val) {
                tail->next = a;
                a = a->next;
            } else {
                tail->next = b;
                b = b->next;
            }
            tail = tail->next;
        }

        tail->next = a ? a : b;

        return head.next;
    }
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) return nullptr;

        int len = lists.size(), i;

        while (len > 1) {
            for (i = 0; i < len / 2; ++i)
                lists[i] = mergeTwoLists(lists[i], lists[len - 1 - i]);

            len = (len + 1) / 2;
        }

        return lists[0];
    }
    
    // O(N log k) time and O(k) space, where N is the total number of nodes.
    ListNode* mergeKListsHeap(vector<ListNode*>& lists) {
        if (lists.empty()) return nullptr;

        auto cmp = [](auto a, auto b) { return a->val > b->val; };
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> q(cmp);

        for (auto list : lists) if (list) q.push(list); // avoid pushing empty lists

        ListNode head, *tail = &head, *node;

        while (!q.empty()) {
            node = q.top();
            q.pop();

            if (node->next) q.push(node->next);

            tail->next = node;
            tail = node;
        }

        return head.next;
    }
};