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

Solution: Using Priority Queue

• First we push all head node to priority queue
• While the queue is not empty, we keep poping node from the queue.
• We also need a dummy head and current pointer.
• Each time we pop a node from queue, we need to push its next node to queue if it exists.

struct MyComp {
    bool operator() (const ListNode* lhs, const ListNode* rhs) {
        return lhs->val > rhs->val;
    }
};

ListNode* mergeKLists(vector<ListNode*>& lists) {
    if (lists.empty()) return NULL;

    ListNode *dummy = new ListNode(0);
    ListNode *cur = dummy;
    priority_queue<ListNode*, vector<ListNode *>, MyComp> q;

    for (auto node: lists) {
        if (node) q.push(node);
    }

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

        cur->next = node;
        cur = cur->next;
        q.pop();

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

    return dummy->next;
}

Solution: Using Heap

We can build a heap using the input lists, then start pop min node from the lists until it's empty.

Note: Remember to remove all null pointers in the lists before building the heap.

    void heapify(vector<ListNode *>& lists, int i) {
        int left = 2*i + 1;
        int right = 2*i + 2;
        int min = i;

        if (left < lists.size() && lists[left]->val < lists[min]->val) {
            min = left;
        }

        if (right < lists.size() && lists[right]->val < lists[min]->val) {
            min = right;
        }

        if (min != i) {
            swap(lists[i], lists[min]);
            heapify(lists, min);
        }
    }

    void removeNullPointers(vector<ListNode*>& lists) {
        int size = 0;
        for (int i=0; i<lists.size(); i++) {
            if (lists[i]) {
                swap(lists[size], lists[i]);
                size += 1;
            }
        }
        while (lists.size() > size) lists.pop_back();

        for (int i=lists.size()/2; i >= 0; i--) {
            heapify(lists, i);
        }
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) return NULL;
        removeNullPointers(lists);

        ListNode *dummy = new ListNode(0);
        ListNode *cur = dummy;
        while (!lists.empty()) {
            ListNode *minNode = lists[0];
            cur->next = minNode;
            cur = minNode;

            if (minNode->next == NULL) {
                lists[0] = lists.back();
                lists.pop_back();
            } else {
                lists[0] = minNode->next;
                minNode->next = NULL;
            }

            heapify(lists, 0);            
        }

        return dummy->next;
    }