LeetCode 023 Merge K Sorted Lists

題：

https://leetcode.com/problems/merge-k-sorted-lists/

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

解法一：将K個連結清單做K-1次歸并，每次歸并是對兩個連結清單的歸并，最終得到一個排序的連結清單。即：

1，2合并，周遊2n個節點；(1,2)與3合并，周遊3n個節點。。。(1...k-1)與k合并，周遊kn個節點。是以總共周遊n*(2+3+...+k)=n*(k^2+k-2)/2，那麼時間複雜度為O(n*k^2)。

解法二：對解法一改進一下，改用分治法，是以時間複雜度變為O(nklogk)。

解法三：将K個連結清單的首元素都取出來，選擇出最小的那個作為新連結清單的head。然後将該元素的next取出來，與其他連結清單的元素比較再選一個小的，放到新連結清單中。選擇出最小元素的時間複雜度為O(k), 總共要選nk次，是以時間複雜度為O(n*k^2)。

解法四：對解法三改進一下，用最小堆來實作選擇最小元素的要求，則時間複雜度降為O(logk)，則總的時間複雜度為O(nklogk)，與解法二的時間複雜度一樣。在Java中，可以使用基于最小堆算法的PriorityQueue來作為最小堆的集合類。代碼如下：

/**
 * 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(List<ListNode> lists) {
        if (lists == null || lists.isEmpty()) {
            return null;
        }
        PriorityQueue<ListNode> minHeap = new PriorityQueue<ListNode>(new Comparator<ListNode>(){
            public int compare(ListNode l1, ListNode l2) {
                return Integer.compare(l1.val, l2.val);
            }
        });
        for (ListNode node : lists) {
            if (node != null) {
                minHeap.add(node);
            }
        }
        ListNode helper = new ListNode(0);
        ListNode next = helper;
        while (!minHeap.isEmpty()) {
            ListNode min = minHeap.poll(); // must not be null
            next.next = min;
            min = min.next;
            if (min != null) {
                minHeap.add(min);
            }
            next = next.next;
        }
        return helper.next;
    }
}