给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
https://leetcode-cn.com/problems/merge-k-sorted-lists/
示例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
Java解法
思路：
- 第一次尝试下困难题，与合并两个有序链表大致相同，尝试用下相同的解法
- 取出每个节点的头节点，调用比较决出头结点，在替换放入下一次比较
- 果然简单，一把过 还是效率差很多
- 使用while 优化内存，但时间还是较差(官方解的分治排序效率不错)
package sj.shimmer.algorithm.ten_2;
import sj.shimmer.algorithm.ListNode;
/**
* Created by SJ on 2021/2/9.
*/
class D16 {
public static void main(String[] args) {
ListNode n1 = ListNode.createNode(new int[]{1,4,5});
ListNode n2 = ListNode.createNode(new int[]{1,3,4});
ListNode n3 = ListNode.createNode(new int[]{2,6});
ListNode n4 = ListNode.createNode(new int[]{});
// System.out.println(mergeKLists(new ListNode[]{n1,n2,n3}));
// System.out.println(mergeKLists(new ListNode[]{}));
// System.out.println(mergeKLists(new ListNode[]{n4}));
System.out.println(mergeKLists2(new ListNode[]{n1,n2,n3}));
System.out.println(mergeKLists2(new ListNode[]{}));
System.out.println(mergeKLists2(new ListNode[]{n4}));
}
public static ListNode mergeKLists2(ListNode[] lists) {
ListNode preHead = new ListNode();
ListNode pre = preHead;
int minIndex = getMin(lists);
while (minIndex!=-1) {
ListNode node = lists[minIndex];
pre.next = node;
pre = pre.next;
lists[minIndex] = node.next;
minIndex = getMin(lists);
}
return preHead.next;
}
public static ListNode mergeKLists(ListNode[] lists) {
ListNode head = null;
int minIndex = getMin(lists);
if (minIndex==-1) {
return null;
}
head = lists[minIndex];
lists[minIndex] = head.next;
head.next = mergeKLists(lists);
return head;
}
public static int getMin(ListNode[] lists) {
ListNode min = null;
int minIndex = -1;
for (int i = 0; i < lists.length; i++) {
if (lists[i] == null) {
continue;
}
if (min == null||min.val>lists[i].val) {
min = lists[i];
minIndex = i;
}
}
return minIndex;
}
}
image
image
官方解
-
顺序合并
利用已有的合并两个有序链表的操作，循环合并
- 时间复杂度： O(k^2 *n)
- 空间复杂度：O(1)
-
分治合并
上一合并的优化，采用分治思想，同时分别合并两个链表
public static ListNode merge(ListNode[] lists,int l,int r) { if (l==r) { return lists[l]; } if (l>r) { return null; } int mid = (r-l)/2+l; return mergeTwoLists(merge(lists,l,mid),merge(lists, mid+1, r)); } public static ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode prehead = new ListNode(-1); ListNode prev = prehead; while (l1 != null && l2 != null) { if (l1.val <= l2.val) { prev.next = l1; l1 = l1.next; } else { prev.next = l2; l2 = l2.next; } prev = prev.next; } // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可 prev.next = l1 == null ? l2 : l1; return prehead.next; }image- 时间复杂度为O(kn×logk)。
- 空间复杂度：递归会使用到 O(logk)
