Merge k sorted linked list

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

One solution is to us a priority queue, or external heap to find the maximal value, coding in java is as follows:

public class Solution {

    public ListNode mergeKLists(ArrayList<ListNode> lists) {

        // Start typing your Java solution below

        // DO NOT write main() function

        if(lists.isEmpty()) return null;

        Comparator<ListNode> comp = new Comparator<ListNode>(){

            public int compare(ListNode a, ListNode b){

                return a.val - b.val;

            }

        };

        PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>(lists.size(),comp);

        for(int i = 0 ; i < lists.size(); i++){

            if(lists.get(i)!=null) queue.add(lists.get(i));

        }

        ListNode root = null; 

        ListNode p = null;

        ListNode node;

        while(queue.size()>0){

            node = queue.poll();

            if(node.next!=null) queue.add(node.next);

            node.next = null;

            if(root == null){

                root = node;

                p = node;

            }

            else{

                p.next = node;

                p = p.next;

            }

        }

        return root;

    }

}

Another solution is directly using the vector storing linked lists as a heap. This is code implemented in C++ using make_heap function



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.size() < 1) return NULL;

    ListNode *head = NULL, *cur = NULL;
    make_heap(lists.begin(), lists.end(), comp());

    while(lists.size() > 0) {
        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;
}

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