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 exceed 104.

题目大意

合并 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. 合并两个有序链表
• 264. 丑数 II
• 2411. 按位或最大的最小子数组长度

- [21. 合并两个有序链表](./0021.md)
- [264. 丑数 II](https://leetcode.com/problems/ugly-number-ii)
- [2411. 按位或最大的最小子数组长度](https://leetcode.com/problems/smallest-subarrays-with-maximum-bitwise-or)