男人女人做性关系网站,吉林建设教育协会网站,掘金网站建设,创建公司策划书题目#xff1a;
给你一个链表数组#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 这题虽然是困难题但是思路很清晰很好理解主要借助最小堆因为最小堆有着将最小的元素置为堆顶的性质所以每次取最小值时将最小堆的头推出即可。 并且使用dummy作为结果的头结点返回。代码及思路如下 创建最小堆 使用 PriorityQueue 作为最小堆并定义比较器来比较节点的值。初始化最小堆 遍历所有链表将每个链表的头节点如果不为空加入最小堆。创建结果链表 使用一个哑节点dummy node来简化头节点的处理。合并过程 当最小堆不为空时重复以下步骤 a. 从堆中取出值最小的节点。 b. 将这个节点添加到结果链表的末尾。 c. 如果这个节点还有下一个节点将下一个节点加入堆中。返回结果 返回哑节点的下一个节点即合并后链表的真正头节点。 复杂度分析 时间复杂度O(N log K)其中 N 是所有节点的总数K 是链表的数量。 每个节点都会被加入和取出堆一次每次堆操作的时间复杂度是 O(log K)。空间复杂度O(K)优先队列中最多同时存在 K 个节点。 import java.util.Comparator;
import java.util.PriorityQueue;public class no_23 {public static void main(String[] args) {ListNode l1 new ListNode(1, new ListNode(4, new ListNode(5)));ListNode l2 new ListNode(1, new ListNode(3, new ListNode(4)));ListNode l3 new ListNode(2, new ListNode(6));ListNode[] lists {l1, l2, l3};// 合并链表ListNode result mergeKLists(lists);// 打印结果while (result ! null) {System.out.print(result.val );result result.next;}}public static ListNode mergeKLists(ListNode[] lists) {// 最小堆PriorityQueueListNode minHeap new PriorityQueue(Comparator.comparingInt(a - a.val));// 将所有的链表头节点加入最小堆for (ListNode head : lists) {if (head ! null) {minHeap.offer(head);}}ListNode dummy new ListNode(0);ListNode tail dummy;while (!minHeap.isEmpty()) {ListNode node minHeap.poll();tail.next node;tail tail.next;if (node.next ! null) {minHeap.offer(node.next);}}return dummy.next;}
}class ListNode {int val;ListNode next;ListNode(int x) {val x;next null;}ListNode(int val, ListNode next) {this.val val;this.next next;}
}
