网站推广外链,棋牌网站开发,网站架构设计师月薪多少,中国国际进口博览会上海这道题主要考察的是归并排序#xff0c;因为已经升序过了#xff0c;更好理解了。
当然也可以采用分治的思路#xff1b;或采用最小堆的思路#xff1b;面试中校招同学写出一种即可#xff0c;如果能全概览讲一下#xff0c;就更加分了。 #############################…这道题主要考察的是归并排序因为已经升序过了更好理解了。
当然也可以采用分治的思路或采用最小堆的思路面试中校招同学写出一种即可如果能全概览讲一下就更加分了。 ##################################################### 给你一个链表数组每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中返回合并后的链表。 示例 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
解题 // 最小堆 public static ListNode mergeKLists(ListNode[] lists) {int k lists.length;ListNode dummyHead new ListNode(0);ListNode tail dummyHead;while (true) {ListNode minNode null;int minPointer -1;for (int i 0; i k; i) {if (lists[i] null) {continue;}if (minNode null || lists[i].val minNode.val) {minNode lists[i];minPointer i;}}if (minPointer -1) {break;}tail.next minNode;tail tail.next;lists[minPointer] lists[minPointer].next;}return dummyHead.next;}public static void main(String[] args) {Solution solution new Solution();ListNode[] lists new ListNode[]{new ListNode(1, new ListNode(4, new ListNode(5))),new ListNode(1, new ListNode(3, new ListNode(4))),new ListNode(2, new ListNode(6))};ListNode list solution.mergeKLists(lists);ListNode.print(list);}
