23. Merge k Sorted Lists
23. Merge k Sorted Lists
🔴 🔖 链表
分治
堆(优先队列)
归并排序
🔗 LeetCode
题目
You are given an array of k
linked-lists lists
, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.
Example 1:
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
1->4->5,
1->3->4,
2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6
Example 2:
Input: lists = []
Output: []
Example 3:
Input: lists = [[]]
Output: []
Constraints:
k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i]
is sorted in ascending order.- The sum of
lists[i].length
will not exceed104
.
题目大意
合并 K 个有序链表
解题思路
借助分治的思想,把 K 个有序链表两两合并即可。相当于是 第 21 题 的加强版。
代码
/**
* @param {ListNode[]} lists
* @return {ListNode}
*/
var mergeKLists = function (lists) {
let len = lists.length;
if (len === 0) return null;
if (len === 1) return lists[0];
const medium = Math.floor(len / 2);
const left = mergeKLists(lists.slice(0, medium));
const right = mergeKLists(lists.slice(medium, len));
return mergeTwoLists(left, right);
};
var mergeTwoLists = function (left, right) {
const res = new ListNode();
let prev = res;
while (left && right) {
if (left.val < right.val) {
prev.next = left;
left = left.next;
} else {
prev.next = right;
right = right.next;
}
prev = prev.next;
}
prev.next = left != null ? left : right;
return res.next;
};
相关题目
相关题目
- [21. 合并两个有序链表](./0021.md)
- [264. 丑数 II](https://leetcode.com/problems/ugly-number-ii)
- [2411. 按位或最大的最小子数组长度](https://leetcode.com/problems/smallest-subarrays-with-maximum-bitwise-or)