leetcode（力扣）之java第十四天

第十四题 合并K个升序链表

给你一个链表数组，每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中，返回合并后的链表。 示例 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 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 /** * 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; } * } PriorityQueue：优先队列 不允许放入null元素，其通过堆实现，具体说是通过完全二叉树（complete binary tree）实现的小顶堆（任意一个非叶子节点的权值，都不大于其左右子节点的权值），也就意味着可以通过数组来作为PriorityQueue的底层实现。 poll()获取并删除队首元素,方法失败时,返回null */ class Solution { public ListNode mergeKLists(ListNode[] lists) { ListNode dummy = new ListNode(0); ListNode head = dummy; //优先队列的作用是能保证每次取出的元素都是队列中权值最小的(权值由传入的比较器决定) PriorityQueue<ListNode> pq = new PriorityQueue<>((o1, o2)-> Integer.compare(o1.val, o2.val)); for(ListNode l : lists){ if(l != null) pq.add(l); } while(!pq.isEmpty()){ ListNode curr = pq.poll();//只是将子列表中第一个值加入到pq中 head.next = curr; head = head.next; //这里添加的是当取出当前最小的数之后，如果该数所在的列表有值，则将该列表的下一个值加入到pq中 if(curr.next != null)pq.add(curr.next); } return dummy.next; } }