23. Merge K Sorted Lists
难度： Hard
刷题内容
原题链接
- https://leetcode.com/problems/merge-k-sorted-lists
内容描述
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Example:
Input:
[
1->4->5,
1->3->4,
2->6
]
解题方案
思路 1 *- 时间复杂度：O(NlogK) - 空间复杂度：O(N)**
K为链表的数量，N为所有链表的节点的总个数
此题在于一分一合，将K个有序链表通过二分，拆成两两一组的链表，就变成了leetcode 21题中的合并两个有序链表了，随后将所有链表逐层合并，就像从二叉树的叶子节点开始，不断向上合并，此题就求解完毕了。
此题需要用到的技巧就是二分，以及递归合并两个有序链表（当然迭代合并两个有序列表也是可以的）
Beats 100%
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) return null;
return sort(lists, 0, lists.length - 1);
}
// 二分K个链表
ListNode sort(ListNode[] lists, int lo, int hi) {
if (lo >= hi) return lists[lo];
int mid = (hi -lo) / 2 + lo;
ListNode l1 = sort(lists, lo, mid);
ListNode l2 = sort(lists, mid + 1, hi);
return merge(l1, l2);
}
// 合并两个有序链表的递归写法
ListNode merge(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
if (l1.val < l2.val) {
l1.next = merge(l1.next, l2);
return l1;
}
l2.next = merge(l2.next, l1);
return l2;
}
