济南物流公司网站建设,网络问卷制作平台,中山模板建站公司,柳州住房和城乡建设局网站目录 【力扣】23. 合并 K 个升序链表题解方法一#xff1a;暴力#xff0c;先遍历取出来值到数组中排序#xff0c;再生成新链表方法二#xff1a;基础堆排序#xff08;使用优先队列 PriorityQueue#xff09;方法三#xff1a;基础堆排序#xff08;使用优先队列 Pri… 目录 【力扣】23. 合并 K 个升序链表题解方法一暴力先遍历取出来值到数组中排序再生成新链表方法二基础堆排序使用优先队列 PriorityQueue方法三基础堆排序使用优先队列 PriorityQueue方法四递归方法五分治 【力扣】23. 合并 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 1 0 4 10^4 104 0 lists[i].length 500 - 1 0 4 10^4 104 lists[i][j] 1 0 4 10^4 104 lists[i] 按升序排列 lists[i].length 的总和不超过 1 0 4 10^4 104
题解
方法一暴力先遍历取出来值到数组中排序再生成新链表
import java.util.*;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) {ListNode dummyNode new ListNode(-1);ListNode prev dummyNode;//先遍历取出来值到数组中排序ListInteger nodes new ArrayList();for(ListNode list: lists){while(list ! null){nodes.add(list.val);list list.next;}}Collections.sort(nodes);//生成新链表for(int x : nodes){prev.next new ListNode(x);prev prev.next;}return dummyNode.next;}
}方法二基础堆排序使用优先队列 PriorityQueue
思路遍历数组每个值建小顶堆照着小顶堆依次取堆顶元素并移除直到堆空
import java.util.*;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 null || lists.length 0) {return null;}//创建一个堆优先队列并设置元素的排序方式PriorityQueueListNode queue new PriorityQueue(new ComparatorListNode() {Overridepublic int compare(ListNode o1, ListNode o2) {return (o1.val - o2.val);}});//遍历链表数组然后将每个链表的每个节点都放入堆中for(ListNode list: lists){while(list ! null){queue.add(list);list list.next;}}ListNode dummyNode new ListNode(-1);ListNode prev dummyNode;//从堆中不断取出元素并将取出的元素串联起来while (!queue.isEmpty()) {prev.next queue.poll();prev prev.next;}prev.next null;return dummyNode.next;}
}方法三基础堆排序使用优先队列 PriorityQueue
思路只遍历每个数组第一个值k 个建小顶堆照着小顶堆依次取堆顶元素并移除移除的同时如果这个值原来还有next 就补齐 k个到堆里继续取堆顶移除。 因为k 个链表中的最小值一定来自 k 个递增链表中某一个的第一个值。将原先的 O(N) 的空间复杂度优化到 O(k) import java.util.*;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 null || lists.length 0) {return null;}//创建一个小根堆并定义好排序函数PriorityQueueListNode queue new PriorityQueue(new ComparatorListNode() {Overridepublic int compare(ListNode o1, ListNode o2) {return (o1.val - o2.val);}});//这里不再是一股脑全部放到堆中,而是只把 k 个链表的第一个节点放入到堆中for (ListNode list : lists) {ListNode eachHead list;if (eachHead ! null) {queue.add(eachHead);}}ListNode dummyNode new ListNode(-1);ListNode prev dummyNode;//之后不断从堆中取出节点如果这个节点所在的链表还有下一个节点就将下个节点也放入堆中while (queue.size() 0) {ListNode node queue.poll();prev.next node;prev prev.next;if (node.next ! null) {queue.add(node.next);}}prev.next null;return dummyNode.next;}
}方法四递归
合并两个链表的思路来合并 k 个链表
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 null || lists.length 0) {return null;}// 将 lists[0] 作为最终合并的链表然后将 list[0] 和 lists[1] 合并成 lists[0-1]// 再将 lists[0-1] 和 lists[2] 合并如此反复最终 lists[0] 就是最终结果ListNode res lists[0];for (int i 1; i lists.length; i) {res merge(res, lists[i]);}return res;}// 合并两个有序链表,递归版本private ListNode merge(ListNode l1, ListNode l2) {//递归的结束条件如果 l1 和 l2 中有一个为空就返回if (l1 null || l2 null) {return (l1 null) ? l2 : l1;}//如果 l1 的值 l2 的值就继续递归比较 l1.next 的值和 l2 的值//l1.next 和 l2 比较完后会产生一个更小的节点 x将 x 加到当前 l1 的后面if (l1.val l2.val) {l1.next merge(l1.next, l2);return l1;}//如果 l1 的值 l2 的值就继续递归比较 l1 的值和 l2.next 的值else {l2.next merge(l1, l2.next);return l2;}}
}方法五分治 一开始数组的规模是 k找到中间点一分为二然后再拆分直到不能再拆分 (规模为1时) 时便返回。之后开始合并合并的代码借用了合并两个排序链表的代码。 当两个规模最小的链表合并完后其规模就变大了然后不断重复这个合并过程直到最终得到一个有序的链表。 分治就是不断缩小其规模再不断合并扩大的过程
class Solution {public ListNode mergeKLists(ListNode[] lists) {// 边界if (lists null || lists.length 0) {return null;}//分治return helper(lists, 0, lists.length - 1);}//通过合并两个链表不断增大其规模整体看就是不断缩小-最后不断扩大的过程private ListNode helper(ListNode[] lists, int begin, int end) {if (begin end) {return lists[begin];}//通过 mid 将数组一分为二并不断缩小规模当规模为 1 时返回并开始合并int mid begin (end - begin) / 2;ListNode left helper(lists, begin, mid);ListNode right helper(lists, mid 1, end);return merge(left, right);}// 合并两个有序链表,递归版本private ListNode merge(ListNode l1, ListNode l2) {//递归的结束条件如果 l1 和 l2 中有一个为空就返回if (l1 null || l2 null) {return (l1 null) ? l2 : l1;}//如果 l1 的值 l2 的值就继续递归比较 l1.next 的值和 l2 的值//l1.next 和 l2 比较完后会产生一个更小的节点 x将 x 加到当前 l1 的后面if (l1.val l2.val) {l1.next merge(l1.next, l2);return l1;}//如果 l1 的值 l2 的值就继续递归比较 l1 的值和 l2.next 的值else {l2.next merge(l1, l2.next);return l2;}}
}
