面试热题（合并K个升序链表）-Toy模板网

这篇具有很好参考价值的文章主要介绍了面试热题（合并K个升序链表）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

请将所有链表合并到一个升序链表中，返回合并后的链表。
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

这道题看似困难题，其实还是比较容易好想的，我们可以维护一个优先最小队列，然后声明一个虚拟头结点，每次出一个最小的节点挂载在已经挂载节点的后面，当队列为空时，就说明我们K个升序列表已经合并完成

面试热题（合并K个升序链表）,热题Hot100,面试,链表

文章来源地址https://www.toymoban.com/news/detail-650324.html

public ListNode mergeKLists(ListNode[] lists) {
     if(lists==null||lists.length==0){
         return null;
     }
     //自定义比较器
     PriorityQueue<ListNode> queue=new PriorityQueue<>(new Comparator<ListNode>() {
         @Override
         public int compare(ListNode o1, ListNode o2) {
             return o1.val-o2.val;
         }
     });
     //将K个节点的头结点入队
     for(ListNode node:lists){
         if(node!=null){
           queue.offer(node);
         }
     }
     //创建一个虚拟头结点
     ListNode dummyNode=new ListNode(-1);
     ListNode curNode=dummyNode;
     while(!queue.isEmpty()){
         ListNode cur=queue.poll();
         curNode.next=cur;
         //更新curNode
         curNode=curNode.next;
         //如果当前节点的next不为空，则让下一个节点进行入队
         if(cur.next!=null){
             queue.offer(cur.next);
         }
     }
     return dummyNode.next;
    }

到了这里，关于面试热题（合并K个升序链表）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！