合并K个有序链表
Wallace Xu 2020-09-25 递归优先队列
# LeetCode 23. 合并K个升序链表 (opens new window)
# 题目描述
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
# 示例
输入：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
输入：lists = []
输出：[]
输入：lists = [[],[]]
输出：[]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 解题思路
我们可以先解决合并两个有序链表的问题，和归并两个有序数组相同，可以使用双指针。我这里为了看起来简洁使用了递归的方法，会使用到O(n)的递归栈空间。
对于头结点保存在数组中的K个链表，我们也可以使用递归的方法，合并两半子数组合并后的链表，递归终止的条件是数组为空或者数组长度小于等于2。
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) return null;
if (lists.length == 1) return lists[0];
if (lists.length == 2) return merge2Lists(lists[0], lists[1]);
return merge2Lists(mergeKLists(Arrays.copyOfRange(lists, 0, lists.length / 2)), mergeKLists(Arrays.copyOfRange(lists, lists.length / 2, lists.length)));
}
private ListNode merge2Lists(ListNode head1, ListNode head2) {
if (head1 == null) return head2;
if (head2 == null) return head1;
if (head1.val <= head2.val) {
head1.next = merge2Lists(head1.next, head2);
return head1;
} else {
head2.next = merge2Lists(head1, head2.next);
return head2;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
除了两两归并的思路外，我们还可以使用大小为K的优先队列来直接管理K个链表当前处理到的节点间的大小关系。
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> a.val - b.val);
for (ListNode node : lists)
if(node != null) heap.offer(node);
ListNode dummy = new ListNode(), pointer = dummy;
while (!heap.isEmpty()) {
ListNode min = heap.poll();
if (min.next != null) heap.offer(min.next);
pointer.next = min;
pointer = pointer.next;
}
return dummy.next;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13