23 Merge k Sorted Lists

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

solution

public ListNode mergeKLists(ListNode[] lists) {

        ListNode header = null;

        //assign each list a pointer
        ArrayList<ListNode> pointers = new ArrayList<ListNode>();

        for(ListNode n : lists) {
            pointers.add(n);
        }

        //compare k Node of current pointers, find smallest one
        ListNode previous = null;
        while(!allIsNull(pointers)) {
            ListNode smallest = compare(pointers);
            //for the header
            if(previous==null) {
                previous = smallest;
                header = previous;
            }
            else {
                //link result
                previous.next = smallest;
                previous = smallest;  
            }

        }

        return header;
    }

    private ListNode compare(ArrayList<ListNode> pointers) {

        //corner case
        if(pointers.size() == 0) return null;

        //find smallest one out of k Node
        ListNode minSoFar = pointers.get(0);
        int minSoFarIndex = 0;
        int index = 0;
        for(ListNode n : pointers) {
            if(n!=null) {
                if(minSoFar==null) {
                    minSoFar = n;
                    minSoFarIndex = index;
                }
                else if(n.val < minSoFar.val) {
                    minSoFar = n;
                    minSoFarIndex = index;
                }
                else {}
            }
            index++; 
        }

        //move pointer of it to its next
        pointers.set(minSoFarIndex, minSoFar.next);

        return minSoFar;

    }

    private boolean allIsNull(ArrayList<ListNode> pointers) {
        for(ListNode n : pointers) {
            if(n != null) return false;
        }
        return true;
    }

复杂度O(NK)

N是Node的总数，要求N次最小点，K是每求一次最小点花的时间

Solution: D&C

public ListNode mergeKLists(ListNode[] lists) {

        //base case
        if(lists.length == 0)
            return null;

        return mergeK(lists, 0, lists.length-1);
    }

    //divide & conqure
    private ListNode mergeK(ListNode[] lists, int low, int high) {

        //corner case
        if(low == high)
            return lists[low];
        if(low + 1 == high)
            return mergeTwo(lists[low], lists[high]);

        //D & C
        int mid = low + (high - low) / 2;
        return mergeTwo(mergeK(lists, low, mid), mergeK(lists, mid+1, high));
    }

    private ListNode mergeTwo(ListNode l1, ListNode l2) {
        //corner case
        if(l1 == null)
            return l2;
        if(l2 == null)
            return l1;

        //find head
        ListNode head, pointer;
        if(l1.val <= l2.val) {
            head = l1;
            l1 = l1.next;
        } else {
            head = l2;
            l2 = l2.next;
        }

        pointer = head;

        //sort other
        while(l1 != null || l2 != null) {
            if(l1 != null && l2 != null) {
                if(l1.val <= l2.val) {
                    pointer.next = l1;
                    l1 = l1.next;
                } else {
                    pointer.next = l2;
                    l2 = l2.next;
                }
            } else if(l1 != null) {
                pointer.next = l1;
                l1 = l1.next;
            } else {
                pointer.next = l2;
                l2 = l2.next;
            }
            pointer = pointer.next;
        }
        return head;
    }

复杂度O(NlgK)

将K划分为lgK级，每次花N的时间比较