Merge k Sorted Lists

Merge k Sorted Lists

This problem is from leetcode.com.

Problem Description:

---

Merge k sorted (ascending order) linked lists and return it as one sorted list. The definition for singly-linked list is:

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

and the function prototype is:

ListNode *mergeKLists(vector<ListNode *> &lists);

Analyze and describe its complexity.

Analysis:

---

This is not a tough problem and there are two ways to solve this kind of k-way merge problem (e.g. merge k sorted arrays):  1) winner/loser tree; 2) minimum heap. Both of them have O(nlog(m)) running time and O(m) space complexity if winner/loser tree and minimum heap are constructed for merge, where n is the total list node number and m is the list number. However, we can achieve O(1) space complexity when the input vector is made as a minimum heap.

For C++, it is easy for us to use several built-in methods in <algorithm> to make a min-heap with a vector and operate on it.

Code (C++):

---

class comp {
public:
    bool operator() (const ListNode* l, const ListNode* r) const {
        return (l->val > r->val);
    }
};

ListNode *mergeKLists(vector<ListNode *> &lists) {
    vector<ListNode*>::iterator it = lists.begin();
    while (it != lists.end()) {
        if(*it == NULL)
            lists.erase(it);
        else
            ++it;
    }
    if(lists.empty())
        return NULL;

    ListNode *head = NULL, *cur = NULL;
    make_heap(lists.begin(), lists.end(), comp());
    while (!lists.empty()) {
        if (head == NULL)
            head = cur = lists[0];
        else
            cur = cur->next = lists[0];

        pop_heap(lists.begin(), lists.end(), comp());
        int last = lists.size() - 1;
        if (lists[last]->next != NULL) {
            lists[last] = lists[last]->next;
            push_heap(lists.begin(), lists.end(), comp());
        } else {
            lists.pop_back();
        }
    }

    return head;
}

-End-