题目地址(23. 合并 K 个排序链表)
https://leetcode-cn.com/problems/merge-k-sorted-lists/description/
题目描述
合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
思路
这道题目是合并 k 个已排序的链表,号称 leetcode 目前最难
的链表题。 和之前我们解决的88.merge-sorted-array很像。
他们有两点区别:
-
这道题的数据结构是链表,那道是数组。这个其实不复杂,毕竟都是线性的数据结构。
-
这道题需要合并 k 个元素,那道则只需要合并两个。这个是两题的关键差别,也是这道题难度为
hard
的原因。
因此我们可以看出,这道题目是88.merge-sorted-array
的进阶版本。其实思路也有点像,我们来具体分析下第二条。
如果你熟悉合并排序的话,你会发现它就是合并排序的一部分
。
具体我们可以来看一个动画
(动画来自 https://zhuanlan.zhihu.com/p/61796021 )
关键点解析
- 分治
- 合并排序(merge sort)
代码
代码支持 JavaScript, Python3
JavaScript Code:
/* * @lc app=leetcode id=23 lang=javascript * * [23] Merge k Sorted Lists * * https://leetcode.com/problems/merge-k-sorted-lists/description/ * */ function mergeTwoLists(l1, l2) { const dummyHead = {}; let current = dummyHead; // l1: 1 -> 3 -> 5 // l2: 2 -> 4 -> 6 while (l1 !== null && l2 !== null) { if (l1.val < l2.val) { current.next = l1; // 把小的添加到结果链表 current = current.next; // 移动结果链表的指针 l1 = l1.next; // 移动小的那个链表的指针 } else { current.next = l2; current = current.next; l2 = l2.next; } } if (l1 === null) { current.next = l2; } else { current.next = l1; } return dummyHead.next; } /** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode[]} lists * @return {ListNode} */ var mergeKLists = function(lists) { // 图参考: https://zhuanlan.zhihu.com/p/61796021 if (lists.length === 0) return null; if (lists.length === 1) return lists[0]; if (lists.length === 2) { return mergeTwoLists(lists[0], lists[1]); } const mid = lists.length >> 1; const l1 = []; for (let i = 0; i < mid; i++) { l1[i] = lists[i]; } const l2 = []; for (let i = mid, j = 0; i < lists.length; i++, j++) { l2[j] = lists[i]; } return mergeTwoLists(mergeKLists(l1), mergeKLists(l2)); };
Python3 Code:
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def mergeKLists(self, lists: List[ListNode]) -> ListNode: n = len(lists) # basic cases if lenth == 0: return None if lenth == 1: return lists[0] if lenth == 2: return self.mergeTwoLists(lists[0], lists[1]) # divide and conqure if not basic cases mid = n // 2 return self.mergeTwoLists(self.mergeKLists(lists[:mid]), self.mergeKLists(lists[mid:n])) def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: res = ListNode(0) c1, c2, c3 = l1, l2, res while c1 or c2: if c1 and c2: if c1.val < c2.val: c3.next = ListNode(c1.val) c1 = c1.next else: c3.next = ListNode(c2.val) c2 = c2.next c3 = c3.next elif c1: c3.next = c1 break else: c3.next = c2 break return res.next
相关题目
-88.merge-sorted-array
LeetCode题解求一根绳子被切两刀能组成一个三角形的概率。如题题解:我们可以设绳长为1,设:- 其中两段长为x, y且x, y都>0- 故第三段长为1-x-y且>0故可以在二维坐标轴画出一个三角形(由x=0;y=0;1-x-y=0围成)要想构成三角形还要满足:- x+y > 1-x-y => x+y > 0.5- x+1-x-y > y => y < 0.5- y+1…
LeetCode题解167.two-sum-ii-input-array-is-sorted题目地址 https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/ 题目描述 这是leetcode头号题目two sum的第二个版本,难度简单。 Given an array of integers that is already sorted in ascendi…
如何告诉Checker遗留方法将接受Nullable类型? - java考虑一下:@Nullable Object obj = null; Optional<Object> optional = Optional.ofNullable(obj); 这会失败,因为检查器框架假定ofNullable无法接受null值(毕竟,其参数未标记为@Nullable)。有没有办法告诉Checker-framework这个方法(或我…
LeetCode题解回文下面的问题,可以用小学三年级的方法解决,也可以使用初中方程式的方法解决,还可以使用大学的高级编程语言解决。请尝试使用所有方法解决,并进行比较。有这样一个乘法算式:```人过大佛寺 * 我 = 寺佛大过人```这里的每一个字代表一个数字,不同的字代表不同的数字,你能把这些数字都找出来么?题解:我这里给出一种“大人的”解法,思路就是从所有可能满足条件的数中暴力搜…
LeetCode题解 最后剩下谁?1〜50号运动员按顺序排成一排。教练下令:“单数运动员出列!”剰下的运动员重新排队编号。教练又下令:“单数运动员出列! ”如此下去,最后只剰下一个人,他是几号运动员?如果教练下的令是“双数运动员出列!”最后剰下的又是谁?题解:## 思路如果是双数出列,那么由于1号从来都没有动过,因此剩下的是1号。如果是单数数列,每次剩下的人的编号分别是$2^N$,其中N为轮…