23. Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

// Min Heap
ListNode* mergeKLists(vector<ListNode*>& lists) { // time: O(Nlogn); space: O(N), N: total listnodes, n: list number
    auto cmp = [] (ListNode*& a, ListNode*& b) {
        return a->val > b->val;
    };
    // minHeap for ListNode
    priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
    for (ListNode*& list : lists) {
        if (list) pq.push(list);
    }
    ListNode *head = nullptr, *pre = nullptr, *tmp = nullptr;
    while (!pq.empty()) {
        tmp = pq.top(); pq.pop();
        if (!pre) head = tmp;
        else pre->next = tmp;
        pre = tmp;
        if (tmp->next) pq.push(tmp->next);
    }
    return head;
}
// struct cmp {
//     bool operator() (ListNode*& a, ListNode*& b) {
//         return a->val > b->val;
//     };
// };

// Make use of mergeTwoLists()
// Iteration
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { // time: O(m + n); space: O(1)
    ListNode *dummy = new ListNode(-1), *pre = dummy;
    while (l1 && l2) {
        if (l1->val < l2->val) {
            pre->next = l1;
            l1 = l1->next;
        } else {
            pre->next = l2;
            l2 = l2->next;
        }
        pre = pre->next;
    }
    if (l1) pre->next = l1;
    else if (l2) pre->next = l2;
    ListNode* res = dummy->next;
    delete dummy;
    return res;
}
// // Recursion
// ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { // time: O(m + n); space: O(m + n)
//     if (!l1) return l2;
//     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;
//     }
// }
ListNode* mergeKLists(vector<ListNode*>& lists) { // time: O(Nlogn)
    if (lists.empty()) return nullptr;
    int n = lists.size();
    while (n > 1) {
        int k = (n + 1) / 2;
        for (int i = 0; i < n / 2; ++i) {
            lists[i] = mergeTwoLists(lists[i], lists[i + k]);
        }
        n = k;
    }
    return lists[0];
}