北海做网站的网络公司,做可视化图表的网站,wordpress 主题 支持文章形式,分享几款做淘客网站的服务器Problem: 23. 合并 K 个升序链表 文章目录 题目描述思路解题方法复杂度Code 题目描述
给你一个链表数组#xff0c;每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中#xff0c;返回合并后的链表。
思路 1.对于合并k个有序链表#xff0c;我们较为容易想… Problem: 23. 合并 K 个升序链表 文章目录 题目描述思路解题方法复杂度Code 题目描述
给你一个链表数组每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中返回合并后的链表。
思路 1.对于合并k个有序链表我们较为容易想到的是用k个指针指向k个链表再依次比较每个指针当前指向节点的值的大小再进行接下来的拼接操作分析易得这种方法的时间复杂度为 O ( k n ) O(kn) O(kn)。 2.我们容易注意到上述主要的操作是每次比较并移动指针且移动的是当前指向节点的值为最小的指针基于以上特点我们可以想到利用最小堆来完成该操作。 解题方法 1.编写内部类QElement。后续创建的最小堆中存储的为指针类型的变量 2.创建最小堆起初将每个链表头节节点添加进去生成一个最小堆 3.创建虚拟头节点和尾指针以便生成结果链表 4.当最小堆不为空时每次取出堆顶元素为ListNode类型指针当栈顶元素的next指针不为空时将其next指针指向的节点再次添加到最小堆中生成一个新的最小堆。 复杂度
时间复杂度: O ( k l o g n ) O(klogn) O(klogn) 空间复杂度: O ( k ) O(k) O(k) Code
/*** 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 {private class QElement {ListNode curNode;public QElement(ListNode curNode) {this.curNode curNode;}}/*** 利用小顶堆合并k个升序链表** param lists 链表头节点数组* return ListNode*/public ListNode mergeKLists(ListNode[] lists) {if (lists null || lists.length 0) {return null;}int len lists.length;;//创建小顶堆PriorityQueueQElement minQueue new PriorityQueue(new ComparatorQElement() {Overridepublic int compare(QElement o1, QElement o2) {return o1.curNode.val - o2.curNode.val;}});//将链表加入到小顶堆for (int i 0; i len; i) {if (lists[i] ! null) {minQueue.offer(new QElement(lists[i]));}}//创建虚拟头节点ListNode dummyNode new ListNode();ListNode tail dummyNode;//当小顶堆不为空时每次取出堆顶元素添加到结果链表while (!minQueue.isEmpty()) {QElement element minQueue.poll();ListNode curNode element.curNode;tail.next element.curNode;tail tail.next;//当前指针已经移动后的指针指向的的下一位不为空if (curNode.next ! null) {minQueue.offer(new QElement(curNode.next));}}return dummyNode.next;}
}
