leetcode: Merge k Sorted Lists

问题描述：

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

原问题链接：https://leetcode.com/problems/merge-k-sorted-lists/

 

问题分析

    这个问题看起来比较复杂，但是结合我前面讨论heap sort和priority queue的文章分析的话，则会发现其实这是一个固定的套路。 

    这个问题的解决思路基本如下。首先用priority queue将整个list里面的每个链表的第一个元素都放入到里面。然后每次从queue里取它的第一个元素。按照priority queue的定义，它最前面的元素必然是最小的元素。然后再判断这个取出来的元素后面是否还有别的元素。有的话则将它后面的那个元素加入到priority queue中间。

    因为要返回一个排序的链表，这里可以创建一个链表的节点，然后用一个节点每次指向从queue里取出的那个元素。然后再往后移动指针。

    这个问题有一个取巧的地方。就是它只适用于链表的情况。因为这里每次取到了队列头部的元素可以顺便拿到它后面的元素。而如果是ArrayList之类的结构则不能得到这样的信息。问题就会要复杂很多。

    总之，根据前面的讨论可以得到如下的代码：

 

/**
 * 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) {
        if(lists == null || lists.length == 0) return null;
        if(lists.length == 1) return lists[0];
        Queue<ListNode> queue = new PriorityQueue<>(lists.length, new Comparator<ListNode>() {
            @Override
            public int compare(ListNode l1, ListNode l2) {
                return l1.val - l2.val;
            }});
        for(ListNode node : lists) {
            if(node != null) queue.add(node);
        }
        ListNode pre = new ListNode(0);
        ListNode head = pre;
        while(!queue.isEmpty()) {
            ListNode temp = queue.poll();
            head.next = temp;
            head = head.next;
            if(temp.next != null) queue.add(temp.next);
        }
        return pre.next;
    }
}

    假设list的长度为k的话，上述代码实现的时间复杂度为O(logK * N)。

 

总结

     这个问题和前面的priority queue，堆排序它们有密切的关系。里面的各种推导和变换有不少值得深究的地方。