23. Merge k Sorted Lists

题目：

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

链接： http://leetcode.com/problems/merge-k-sorted-lists/

题解：

使用min heap构建的priority queue， 遍历输入数组，将非空表头节点加入min PQ，每次从PQ中poll()出最小值作为当前结果，之后加入取出节点的下一个非空节点。 当min PQ为空时结束。

Time Complexity - O(nlogn)， Space Complexity - O(m)， m为输入数组的length

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ListNode[] lists) { // using priority queue (min heap)
        if(lists == null || lists.length == 0)
            return null;
        PriorityQueue<ListNode> minPQ = new PriorityQueue<ListNode>(lists.length, 
            new Comparator<ListNode>(){
                public int compare(ListNode a, ListNode b) {
                    if(a.val < b.val)
                        return -1;
                    else if(a.val > b.val)
                        return 1;
                    else
                        return 0;
                }
            });
        
        for(ListNode node : lists) {
            if(node != null)
                minPQ.offer(node);
        }
            
        
        ListNode dummy = new ListNode(-1);
        ListNode node = dummy;
        
        while(minPQ.size() > 0) {
            ListNode tmp = minPQ.poll();
            node.next = tmp;
            if(tmp.next != null)
                minPQ.offer(tmp.next);
            node = node.next;
        }
        
        return dummy.next;
    }
}

二刷：

Java:

跟一刷一样，也是先建立一个自带Comparator的min-oriented PriorityQueue。初始把所有非空list head都放进pq， 之后poll出当前最小的值设置为node.next，假如这条list非空，则将其之后的节点作为head放入pq中继续进行比较。这里insert和deleteMin操作复杂度都是O(logk)，k是lists.length

Time Complexity - O(nlogk)， Space Complexity - O(k)，  这里k为lists的长度，  n为所有的节点数

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode dummy = new ListNode(-1);
        ListNode node = dummy;
        PriorityQueue<ListNode> pq = new PriorityQueue<ListNode>(new Comparator<ListNode>() {
            public int compare(ListNode l1, ListNode l2) {
                return l1.val - l2.val;
            }
            });
        for (ListNode head : lists) {
            if (head != null) {
                pq.offer(head);
            }
        }
        while (pq.size() > 0) {
            node.next = pq.poll();
            node = node.next;
            if (node.next != null) {
                pq.offer(node.next);
            }
        }
        return dummy.next;
    }
}

下面是把匿名Comparator换成了使用了Lambda expression， 但是巨慢无比。可能JVM还没有很好的优化。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode dummy = new ListNode(-1);
        ListNode node = dummy;
        PriorityQueue<ListNode> pq = new PriorityQueue<ListNode>((ListNode l1, ListNode l2) -> l1.val - l2.val);
        for (ListNode head : lists) {
            if (head != null) {
                pq.offer(head);
            }
        }
        while (pq.size() > 0) {
            node.next = pq.poll();
            node = node.next;
            if (node.next != null) {
                pq.offer(node.next);
            }
            node.next = null;
        }
        return dummy.next;
    }
}

Python:

还是不熟悉Python，好难写，多参考了cbmbbz，放了tuple在pq里。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
from Queue import PriorityQueue

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        dummy = ListNode(None)
        node = dummy
        pq = PriorityQueue();
        for head in lists:
            if head:
                pq.put((head.val, head))
        while pq.qsize() > 0:
            node.next = pq.get()[1]
            node = node.next
            if node.next:
                pq.put((node.next.val, node.next))
        return dummy.next
        

需要继续学习heap的原理，heapify - swim up or sink down，bionomial heap等等。

Reference:

https://leetcode.com/discuss/9279/a-java-solution-based-on-priority-queue

http://algs4.cs.princeton.edu/24pq/

https://leetcode.com/discuss/78758/10-line-python-solution-with-priority-queue

https://leetcode.com/discuss/55662/108ms-python-solution-with-heapq-and-avoid-changing-heap-size