Merge k Sorted Lists

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

---------------------------第一遍-------------Merge every two list---------------

public class Solution {
      public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if (lists == null || lists.size() == 0) {
            return null;
        }
        // every time, find two shortest list, and merge them
        ListNode header = new ListNode(Integer.MIN_VALUE);
        header.next = lists.remove(0);

        while (!lists.isEmpty()) {
            // merge the second onto the first
            ListNode curHeader = new ListNode(0);
            curHeader.next = lists.remove(0);
            // add merge two list
            header = merge2List(header, curHeader);
        }
        return header.next;
    }

    private ListNode merge2List(ListNode header1, ListNode header2) {
        ListNode runner1 = header1;
        while (header2.next != null) {
            // detach first node of header2 list
            ListNode tmp = header2.next;
            header2.next = header2.next.next; // delete tmp node
            // find runner1 , such that runner1.val <
            while (runner1.next != null && runner1.next.val < tmp.val) {
                runner1 = runner1.next;
            }
            tmp.next = runner1.next;
            runner1.next = tmp;
            runner1 = runner1.next; // point to the next possible value
        }
        return header1;
    }
}

其实，网上有个用heap来做的。但是，需要自己动手写comparator，这个正是爷们儿的弱项。需要多写几个。

public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists==null || lists.length ==0)
            return null;
        ListNode header = new ListNode(0);
        ListNode tail = header;
        PriorityQueue<ListNode> minHeap = new PriorityQueue<ListNode>(lists.length,new Comparator<ListNode>(){
            public int compare(ListNode a, ListNode b){
                return a.val - b.val;
            }
        });
        for(int i =0;i<lists.length;i++)
            if(lists[i]!=null)
                minHeap.add(lists[i]);
        while( !minHeap.isEmpty()){
            ListNode tmp = minHeap.poll();
            tail.next = tmp;
            tail = tail.next;
            if(tmp.next!=null)
                minHeap.add(tmp.next);
        }
        return header.next;
    }
}

Mistakes:
1: 检查了输入的null,但是没有检查当 size() == 0的时候的情况
2:  由于merge 的时候，我们用了header 来， 所以返回的时候， 原本的list head 可能已经改变了，所以需要给 mergeTwoList() 一个返回值，并  主动设置 i_{th} position  of the given ArrayList.
3: 当加入到preNode 和 curNode 之间时，  要记得  重新设置 preNode到 curNode之前。  以保持一致。
4: 汗， 加入到尾部的时候，也要重新设置curNode， 郁闷中~~~~~~~~~~总是犯错
                curNode = tmp;

Learned: