[leetcode-排序]--23. Merge k Sorted Lists

r囧r小猫 2022-07-11 23:57 85阅读 0赞

Question 23. Merge k Sorted Lists

> Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
> 
> 中文：合并k个有序的链表，然后返回一个有序的链表的表头结点。

解决思路：

## 1) 模仿两个链表的做法： ##

用一个链表数组ListNode\[\] ps 来保存每个链表的索引，然后每次比较的时候，就是找出 ps数组 中的最小值，其余思想和Question21 基本一样，这个时候的缺点就是：每次找最小值都用进行一次遍历ps数组，时间复杂度是O(k), 这样整体的时间开销就比较大了。

这种思路我就不给出代码了，和Question21一样的套路，唯一就是需要一个另外的函数来计算 ps 数组的最小值。

## 2）使用Java中的PriorityQueue解决 ##

先看看PriorityQueue的构造函数：

public PriorityQueue(int initialCapacity, Comparator<? super E> comparator)

使用指定的初始容量创建一个 PriorityQueue，并根据指定的比较器对元素进行排序。

里面的有序性就是由PriorityQueue维护的：

/** * 这是由Java的PriorityQueue来维护有序性. * @param lists 链表头结点数组 * @return */
    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists==null || lists.length==0)
            return null;
    
        //队列中的元素是按照从小到大排序的
        PriorityQueue<ListNode> queue= new PriorityQueue<ListNode>(lists.length, new Comparator<ListNode>(){
            @Override
            public int compare(ListNode o1,ListNode o2){
                if (o1.val<o2.val)
                    return -1;
                else if (o1.val==o2.val)
                    return 0;
                else
                    return 1;
            }
        });
    
        //头结点
        ListNode dummy = new ListNode(0);
        ListNode tail=dummy;
    
        //将每个链表的头结点放入队列
        for (ListNode node:lists)
            if (node!=null)
                queue.add(node);
    
        while (!queue.isEmpty()){
            tail.next=queue.poll();//获取并移除此队列的头，如果此队列为空，则返回 null。
            tail=tail.next;
    
            if (tail.next!=null)
                queue.add(tail.next);
        }
        return dummy.next;
    }