23. Merge k Sorted Lists

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

思路：妙在建定长Priority Queue然后反复使用

public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists==null||lists.length==0){
            return null;
        }

        Comparator<ListNode> comparator = new Comparator<ListNode>(){
            public int compare(ListNode list1, ListNode list2){
                int val1 = list1.val;
                int val2 = list2.val;
                return val1-val2;
            }
        };

        PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>(lists.length, comparator);

        ListNode newHead = new ListNode(0);
        ListNode p = newHead;

        for (int i=0;i<lists.length;i++){
            ListNode list = lists[i];
            while(list!=null){
                queue.add(list);
                list = list.next;
            }
        }
        while(!queue.isEmpty()){
            p.next = queue.remove();
            p = p.next;
        }
        p.next = null;
        return newHead.next;
    }
}

C++ code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode  *mergeKLists(vector<ListNode*> &lists) {
        if (lists.empty()) return nullptr;

        while (lists.size()>1){
            lists.push_back(mergeTwoLists(lists[0],lists[1]));
            lists.erase(lists.begin());
            lists.erase(lists.begin());
        }
        return lists.front();
    }

    ListNode * mergeTwoLists(ListNode* l1, ListNode* l2){
        if(l1 == nullptr){
            return l2;
        }
        if(l2 == nullptr){
            return l1;
        }
        if(l1->val <= l2->val){
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        }
        else{
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};