题解 | #合并k个已排序的链表#
合并k个已排序的链表
https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param lists ListNode类ArrayList * @return ListNode类 */ public ListNode mergeKLists (ArrayList<ListNode> lists) { // write code here Queue<ListNode> priorityQueue = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);//创造小根堆 for (int i = 0; i < lists.size(); i++) { if (lists.get(i) != null) { priorityQueue.add(lists.get(i)); } } ListNode res = new ListNode(-1); ListNode head = res; while (!priorityQueue.isEmpty()) { ListNode tmp = priorityQueue.poll(); head.next = tmp; head = head.next; //将tmp链表的下一个节点加入小根堆 if (tmp.next != null) { priorityQueue.add(tmp.next); } } return res.next; } }
最小值问题,多去想象小根堆实现,小根堆的维护确保了堆顶一定是最小元素