题目
LeetCode.23.合并K个升序链表（困难）
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
题解
解法1：优先队列
普通二路归并排序直接比较两个链表首元素即可。
多个链表首元素怎么比较？
用优先队列，构建小顶堆，每次加入一个节点，优先队列。
调整一次堆需要O(log k)时间，k为列表个数。
由于要把所有节点都加入堆中，设链表节点总数为n，总时间复杂度为O(n * log k)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| import java.util.*
class Solution {
fun mergeKLists(lists: Array<ListNode?>): ListNode? {
val pq = PriorityQueue<ListNode> { n1, n2 -> n1.`val` - n2.`val` }
val dummy = ListNode(0)
var p: ListNode? = dummy
lists.forEach { node -> if (node != null) pq.add(node) }
while (pq.isNotEmpty()) {
val smallest = pq.poll()
if (smallest.next != null) {
pq.add(smallest.next)
}
p?.next = smallest
p = p?.next
}
val newHead = dummy.next
dummy.next = null
return newHead
}
}
|
解法2：分治
对所有链表两两归并，这样每次链表数量减半，假设总共有k个链表，需要归并log k次。
假设所有链表结点总数为n，每一次的两两归并都要遍历所有结点，总时间复杂度为O(n * log k)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| import java.util.*
class Solution {
fun mergeKLists(lists: Array<ListNode?>): ListNode? {
if (lists.isEmpty()) return null
return merge(lists, 0, lists.size - 1)
}
fun merge(lists: Array<ListNode?>, low: Int, high: Int): ListNode? {
if (low == high) return lists[low]
val mid = low + (high - low) / 2;
val l1 = merge(lists, low, mid);
val l2 = merge(lists, mid + 1, high);
return mergeTwoList(l1, l2);
}
fun mergeTwoList(l1: ListNode?, l2: ListNode?): ListNode? {
val dummy = ListNode(0)
var tail: ListNode? = dummy
var p1 = l1
var p2 = l2
while (p1 != null && p2 != null) {
if (p1.`val` < p2.`val`) {
tail?.next = p1
p1 = p1?.next
} else {
tail?.next = p2
p2 = p2?.next
}
tail = tail?.next
}
tail?.next = if (p1 != null) p1 else p2
val newHead = dummy.next
dummy.next = null
return newHead
}
}
|