朋友圈链接怎么制作,福州seo网站优化,工信部网站备案文件,重庆装修协会题干描述
23. 合并 K 个升序链表
给你一个链表数组#xff0c;每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中#xff0c;返回合并后的链表。 示例 1#xff1a;
输入#xff1a; lists [[1,4,5],[1,3,4],[2,6]]
输出#xff1a; [1,1,2,3,4,4,5,6]…题干描述
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.length0 k 10^40 lists[i].length 500-10^4 lists[i][j] 10^4lists[i] 按 升序 排列lists[i].length 的总和不超过 10^4
分析解答
合并多个升序数组乍眼一看这我不会啊
但如果将多个改为合并两个想必大家都会做了。依次比较两个链表的每一个节点把它们连接起来即可。
那么多个不会两个一眼就能想到解决办法的这部分问题可以采用一个通用思想分治
使用一个递归的 helper 帮助我们将多个链表逐步拆分为两个。两个解决了那么 K 个也就解决了。
代码如下
/*** Definition for singly-linked list.* function ListNode(val, next) {* this.val (valundefined ? 0 : val)* this.next (nextundefined ? null : next)* }*/
function ListNode(val, next) {this.val (val undefined ? 0 : val)this.next (next undefined ? null : next)
}/*** param {ListNode[]} lists* return {ListNode}*/
var mergeKLists function (lists) {if (!lists.length) return null;return mergeHelper(lists, 0, lists.length - 1);
};
const mergeHelper (lists, left, right) {if (left right) return lists[left];let mid Math.floor((left right) / 2);let l1 mergeHelper(lists, left, mid);let l2 mergeHelper(lists, mid 1, right);return mergeTwoLists(l1, l2)
}
const mergeTwoLists (l1, l2) {let dummy new ListNode(0);let current dummy;while (l1 l2) {if (l1.val l2.val) {current.next l1;l1 l1.next;} else {current.next l2;l2 l2.next;}current current.next;}current.next l1 || l2;return dummy.next;
}思路拓展
除了分治我们还有什么其他方法吗
