建设网站教程2016,网站的引导页面是什么意思,wordpress主题 红木,地方网站 源码题目描述给你一个链表数组#xff0c;每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中#xff0c;返回合并后的链表。示例 1#xff1a;输入#xff1a;lists [[1,4,5],[1,3,4],[2,6]]输出#xff1a;[1,1,2,3,4,4,5,6]解释#xff1a;链表数组如下…题目描述给你一个链表数组每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中返回合并后的链表。 示例 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.length0 k 10^40 lists[i].length 500-10^4 lists[i][j] 10^4lists[i] 按 升序 排列lists[i].length 的总和不超过 10^4来源力扣LeetCode链接https://leetcode.cn/problems/merge-k-sorted-lists著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。思路这是一道面试算法题好久没有练习。面试紧张写得很慢。合并K个升序链表每个链表的长度不一致。可以利用优先队列的性质进行编程。首先定义优先队列的排序方式根据节点进行排序核心代码每次弹出最小的元素依次往后排序。遍历整个优先队列直到队列为空。代码/*** 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; }* }*/
class Solution {public ListNode mergeKLists(ListNode[] lists) {if(lists.length 0){return null;}ListNode dummyHead new ListNode(0);ListNode curr dummyHead;PriorityQueueListNode pq new PriorityQueue(new ComparatorListNode(){public int compare(ListNode o1,ListNode o2){return o1.val-o2.val;}});for(ListNode list:lists){if(listnull){continue;}pq.add(list);}while(!pq.isEmpty()){ListNode nextNode pq.poll();curr.nextnextNode;curr curr.next;if(nextNode.next!null){pq.add(nextNode.next);}}return dummyHead.next;}
}
