【数据结构与算法】力扣 23. 合并 K 个升序链表

题干描述

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.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i] 按 升序 排列
• lists[i].length 的总和不超过 10^4

分析解答

合并多个升序数组，乍眼一看这？我不会啊？

但如果将多个改为合并两个，想必大家都会做了。依次比较两个链表的每一个节点，把它们连接起来即可。

那么多个不会，两个一眼就能想到解决办法的这部分问题，可以采用一个通用思想：分治！

使用一个递归的 helper 帮助我们将多个链表逐步拆分为两个。两个解决了，那么 K 个也就解决了。

代码如下：

/*** Definition for singly-linked list.* function ListNode(val, next) {*     this.val = (val===undefined ? 0 : val)*     this.next = (next===undefined ? 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;
}

思路拓展

除了分治，我们还有什么其他方法吗？