Leetcode刷题100天—23. 合并K个升序链表(优先队列)—day18

亦凉 2022-09-11 03:18 187阅读 0赞

前言：

> 作者：神的孩子在歌唱
> 
> 大家好，我叫运智

![image-20210825213726626][]

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

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：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

示例 2：

输入：lists = []
    输出：[]

示例 3：

输入：lists = [[]]
    输出：[]

提示：

*  k == lists.length
 *  0 <= k <= 10^4
 *  0 <= lists\[i\].length <= 500
 *  \-10^4 <= lists\[i\]\[j\] <= 10^4
 *  lists\[i\] 按 升序 排列
 *  lists\[i\].length 的总和不超过 10^4

> 来源：力扣（LeetCode）  
> 链接：https://leetcode-cn.com/problems/merge-k-sorted-lists  
> 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

package 优先队列;
    
    import java.util.PriorityQueue;
    
    /* * https://leetcode-cn.com/problems/merge-k-sorted-lists/ */
    public class _23_合并K个升序链表 { 
        public ListNode mergeKLists(ListNode[] lists) { 
    // 新建一个链表
        	ListNode head=new ListNode(0,null);
    // 建立指针
        	ListNode node=head;
    
    // 创建队列
        	PriorityQueue<Integer> queue =new PriorityQueue<>();
    // for循环取出数组中的队列，在通过while循环取出链表中的值存入队列中
        	for(ListNode list:lists) { 
        		while(list!=null) { 
        			queue.offer(list.val);
    // 使用指针连接后面的list，最后就连接好了head
        			node.next=list;
        			node=node.next;
        			list=list.next;
        		}
        	}
    // 重新设置指针
        	ListNode node1=head.next;
    // 在通过循环取出队列中的值修改链表中的值 
        	while(!queue.isEmpty()) { 
        		int num=queue.poll();
        		System.out.print(num);
        		node1.val=num;
        		node1=node1.next;
        	}
        	return head.next;
        }
    }

> 本人csdn博客：https://blog.csdn.net/weixin\_46654114
> 
> 转载说明：跟我说明，务必注明来源，附带本人博客连接。

[image-20210825213726626]: /images/20220828/de2655695b6f4cb5ba9319c5e7acefa4.png