Merge k Sorted Lists

Description

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

Hint

Train of

//1: recursion, divide lists into left and right until there are two lists left, and merge them

//2: priority queue

Code

public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length == 0)
        return null;
        return merge(lists, 0, lists.length - 1);
    }
    public ListNode merge(ListNode[] lists, int low, int high){
        if(low < high){
            int mid = (low + high) / 2;
            ListNode left = merge(lists, low , mid);
            ListNode right = merge(lists, mid + 1, high);
            return mergeTwoLists(left, right);
        }
        return lists[low];//low >= high时候直接返回low
    }
    public ListNode mergeTwoLists(ListNode l1, ListNode l2){
        ListNode fake = new ListNode(-1);
        ListNode l3 = fake;
        while(l1 != null && l2 != null) {
            if(l1.val < l2.val) {
                l3.next = l1;
                l1 = l1.next;
            } else {
                l3.next = l2;
                l2 = l2.next;
            }
            l3 = l3.next;
        }
        if(l1 != null) {
            l3.next = l1;
        }
        if(l2 != null) {
            l3.next = l2;
        }
        return fake.next;

    }
}


//method2:
public class Solution {
    public ListNode mergeKLists(List<ListNode> lists) {
        if (lists==null||lists.size()==0) return null;

        PriorityQueue<ListNode> queue= new PriorityQueue<ListNode>(lists.size(),new Comparator<ListNode>(){
            @Override
            public int compare(ListNode o1,ListNode o2){
                if (o1.val<o2.val)
                    return -1;
                else if (o1.val==o2.val)
                    return 0;
                else 
                    return 1;
            }
        });

        ListNode dummy = new ListNode(0);
        ListNode tail=dummy;

        for (ListNode node:lists)
            if (node!=null)
                queue.add(node);

        while (!queue.isEmpty()){
            tail.next=queue.poll();
            tail=tail.next;

            if (tail.next!=null)
                queue.add(tail.next);
        }
        return dummy.next;
    }
}

Complexity

Suppose the total number of nodes is n The total time complexity if (n * log k) .For a priority queue, insertion takes logK time