合并 K 个升序链表

这篇文章会收录到 :算法通关村第十四关-白银挑战堆的经典问题-CSDN博客

合并 K 个升序链表

描述 :

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并服务器托管网到一个升序链表中，返回合并后的链表。

题目 :

LeetCode 23. 合并 K 个升序链表 :

23. 合并 K 个升序链表

分析 :

我们看堆排序如何解决。因为每个队列都是从小到大排序的，我们每次都要找最小的元素，所以我们要用小根堆，构建方法和操作与大顶堆完全一样，不同的是每次比较谁更小。使用堆合并的策略是不管几个链表，最终都是按照顺序来的。每次都将剩余节点的最小值加到输出链表尾部，然后进行堆调整，最后堆空的时候，合并也就完成了还有一个问题，这个堆应该定义为多大呢? 给了几个链表，堆就定义多大。

解析 :

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    pub服务器托管网lic ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length == 0){
            return null;
        }
        PriorityQueue pq = new PriorityQueue(Comparator.comparing(node -> node.val));
        for(int i = 0;i

这期就到这里 , 下期见!

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net