一、题目粗心
标签: 栈和队列
https://leetcode.cn/problems/...
给你一个链表数组，每个链表都曾经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 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 <= listsi <= 10^4
- lists[i] 按 升序 排列
- lists[i].length 的总和不超过 10^4
二、解题思路
这里须要将k个排序链表交融成一个排序链表，多个输出一个输入，相似于漏斗，因而能够利用最小堆的概念。
取每个Linked List的最小节点放入一个heap中，排成最小堆，而后取出堆顶最小的元素放入合并的List中，而后将该节点在其对应的List中的下一个节点插入到heap中，循环下面步骤。
三、解题办法
3.1 Java实现
public class Solution { public ListNode mergeKLists(ListNode[] lists) { PriorityQueue<ListNode> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o.val)); for (ListNode node : lists) { if (node != null) { pq.add(node); } } ListNode ret = null; ListNode cur = null; while (!pq.isEmpty()) { ListNode node = pq.poll(); if (ret == null) { cur = node; ret = cur; } else { cur.next = node; cur = cur.next; } if (node.next != null) { pq.add(node.next); } } return ret; } /** * 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; } }}四、总结小记
- 2022/8/11 疫情常态化了