23. Merge k Sorted Lists

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

Solution1：堆排序

建立一个大小为k的小顶堆，用来排出堆中最小的元素。分别先将k个list中的第一个元素加入堆中，这样从堆中得到的node是全局最小的 并将这个node在list中的下一个node加入堆中，这样再从堆中得到的node是全局第二小的，以此类推得到从小到大merged排序好的result_list。

suppose n is the total number of nodes.
Time Complexity: O(logk * n) Space Complexity: O(k)

Solution2：Divide and Conquer

两两merge，再两两merge...，
merge一次最多O(n)，merge了log(k)次。

suppose n is the total number of nodes.
Time Complexity: O(logk * n) Space Complexity: O(n + logk) 递归缓存

Solution1 Code：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> queue = new PriorityQueue<>((x, y) -> x.val - y.val);
        
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        
        for(int i = 0; i < lists.length; i++) {
            if(lists[i] != null) {
                queue.offer(lists[i]);
            }
        }
        
        while(!queue.isEmpty()) {
            cur.next = queue.poll();
            cur = cur.next;
            if(cur.next != null) {
                queue.offer(cur.next);
            }
        }
        
        return dummy.next;
    }
}

Solution2 Code：

class Solution2 {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length == 0) return null;
        return partion(lists, 0, lists.length - 1);
    }

    private ListNode partion(ListNode[] lists, int start, int end) {
        if(start == end) return lists[start];
        else if(start < end) {
            int mid = (start + end) / 2;
            ListNode l1 = partion(lists, start, mid);
            ListNode l2 = partion(lists, mid + 1, end);
            return merge(l1, l2);
        }
        else {
            //not gonna happen.
            return null;
        } 
    }

    private ListNode merge(ListNode l1, ListNode l2) {
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        if(l1.val < l2.val) {
            l1.next = merge(l1.next, l2);
            return l1;
        } else {
            l2.next = merge(l1, l2.next);
            return l2;
        }
    }
}