LeetCode #23 Merge k Sorted Lists (H)

[Problem]

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

 

[Analysis]

这题一上来，就会想到之前做过的Merge Two Sorted Lists。但是如果单纯地不断将新的list merge进结果，复杂度是非常高的，因为仔细想想就会发现在这个过程中结果里已经merge过的元素需要被重新排序，而这一部分无用功是可以通过使用合理的技巧优化的。这里需要用到的是heap数据结构。想到heap之后的步骤就比较简单了，只需要将所有list head放进heap，每次取出顶部的一个链接到结果里，并将它的next放进heap（假如存在），直至heap为空也就是所有元素都访问过一遍。其中存取元素以及链接的复杂度都是O(1)，而heap存入新元素的复杂度是O(log(k))，于是整个算法的复杂度就是O(log(k) * n)，n为所有list里元素的个数之和。

*注意有很多null case需要判断。

*在Java里面heap的implementation是PriorityQueue。

 

[Solution]

 

import java.util.Comparator;
import java.util.PriorityQueue;

public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {        
        int size = lists.length;
        if (size == 0) {
            return null;
        }
        
        if (size == 1) {
            return lists[0];
        }
        
        PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>(
            2, 
            new Comparator<ListNode>() {
                @Override
                public int compare(ListNode node1, ListNode node2) {
                    return node1.val - node2.val;
                }
            }
        );
        
        for (ListNode node : lists) {
            if (node != null) {
                heap.add(node);
            }
        }                
        
        ListNode head = null;
        ListNode cur = null;
        
        while (!heap.isEmpty()) {
            ListNode node = heap.poll();                        
            
            if (node.next != null) {
                heap.add(node.next);
            }
            
            if (head == null) {
                head = node;
                cur = node;
            } else {
                cur.next = node;
                cur = cur.next;
            }
        }
        
        return head;
    }    
}