Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Solution1: divide and conquer
类似于MergeSort的思路,就是分治法，是一个比较经典的O(nlogn)的排序算法. 思路是先分成两个子任务，然后递归求子任务，最后回溯回来。这个题目也是这样，先把k个list分成两半，然后继续划分，知道剩下两个list就合并起来，合并时会用到Merge Two Sorted Lists这道题. 
假设总共有k个list，每个list的最大长度是n，那么运行时间满足递推式T(k) = 2T(k/2)+O(n*k)。可以算出算法的总复杂度是O(nklogk)。空间复杂度的话是递归栈的大小O(logk)。
分析链接：http://blog.csdn.net/linhuanmars/article/details/19899259

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ArrayList lists) {
        if(lists == null || lists.size() == 0)
            return null;
        
        return helper(lists, 0, lists.size() - 1);
    }
    
    //divide
    public ListNode helper(ArrayList lists, int left, int right) {
        if(left < right) {
            int mid = (left + right) / 2;
            return merge(helper(lists, left, mid), helper(lists, mid+1, right));
        }
        return lists.get(left);
    }
    
    //merge, similar as merge two sorted lists
    public ListNode merge(ListNode l1, ListNode l2) {
        ListNode newHead = new ListNode(0);
        newHead.next = l1;
        ListNode cur = newHead;
        while(l1 != null && l2 != null) {
            if(l1.val < l2.val) {
                l1 = l1.next;
            }else {
                ListNode next = l2.next;
                cur.next = l2;
                l2.next = l1;
                l2 = next;
            }
            cur = cur.next;
        }
        
        if(l2 != null) {
            cur.next = l2;
        }
        
        return newHead.next;
    }
}

Solution2: priority queue
The simplest solution is using PriorityQueue. The elements of the priority queue are ordered according to their natural ordering, or by a comparator provided at the construction time (in this case).
用到了堆的数据结构heap。维护一个大小为k的堆，每次取堆顶的最小元素放到结果中，然后读取该元素的下一个元素放入堆中，重新维护好。因为每个链表是有序的，每次又是去当前k个元素中最小的，所以当所有链表都读完时结束，这个时候所有元素按从小到大放在结果链表中。
这个算法每个元素要读取一次，即是k*n次，然后每次读取元素要把新元素插入堆中要logk的复杂度，所以总时间复杂度是O(nklogk)。空间复杂度是堆的大小，即为O(k)。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ArrayList lists) {
        if(lists == null || lists.size() == 0)
            return null;
        
        PriorityQueue heap = new PriorityQueue(10, new Comparator() {
            @Override
            public int compare(ListNode l1, ListNode l2) {
                return l1.val - l2.val;
            }
        });
        
        for(int i = 0; i < lists.size(); i++) {
            ListNode node = lists.get(i);
            if(node != null) {
                //store the first node of every list
                //heap are ordered by the comparator
                heap.offer(node);  
            }
        }
        
        ListNode head = null;
        ListNode pre = head;
        while(heap.size() > 0) {
            ListNode cur = heap.poll();
            if(head == null) {
                head = cur;
                pre = head;
            }else {
                pre.next = cur;
            }
            pre = cur;
            if(cur.next != null) {
                heap.offer(cur.next); //store next element in this list into heap
            }
        }
        
        return head;
    }
}