题目:
给你一个链表数组,每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中,返回合并后的链表。
示例 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
这题虽然是困难题,但是思路很清晰,很好理解,主要借助最小堆,因为最小堆有着将最小的元素置为堆顶的性质,所以每次取最小值时将最小堆的头推出即可。
并且使用dummy作为结果的头结点返回。代码及思路如下:
- 创建最小堆:
- 使用
PriorityQueue
作为最小堆,并定义比较器来比较节点的值。- 初始化最小堆:
- 遍历所有链表,将每个链表的头节点(如果不为空)加入最小堆。
- 创建结果链表:
- 使用一个哑节点(dummy node)来简化头节点的处理。
- 合并过程:
- 当最小堆不为空时,重复以下步骤:
a. 从堆中取出值最小的节点。
b. 将这个节点添加到结果链表的末尾。
c. 如果这个节点还有下一个节点,将下一个节点加入堆中。- 返回结果:
- 返回哑节点的下一个节点,即合并后链表的真正头节点。
复杂度分析
- 时间复杂度:O(N log K),其中 N 是所有节点的总数,K 是链表的数量。
每个节点都会被加入和取出堆一次,每次堆操作的时间复杂度是 O(log K)。- 空间复杂度:O(K),优先队列中最多同时存在 K 个节点。
import java.util.Comparator;
import java.util.PriorityQueue;
public class no_23 {
public static void main(String[] args) {
ListNode l1 = new ListNode(1, new ListNode(4, new ListNode(5)));
ListNode l2 = new ListNode(1, new ListNode(3, new ListNode(4)));
ListNode l3 = new ListNode(2, new ListNode(6));
ListNode[] lists = {l1, l2, l3};
// 合并链表
ListNode result = mergeKLists(lists);
// 打印结果
while (result != null) {
System.out.print(result.val + " ");
result = result.next;
}
}
public static ListNode mergeKLists(ListNode[] lists) {
// 最小堆
PriorityQueue<ListNode> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a.val));
// 将所有的链表头节点加入最小堆
for (ListNode head : lists) {
if (head != null) {
minHeap.offer(head);
}
}
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (!minHeap.isEmpty()) {
ListNode node = minHeap.poll();
tail.next = node;
tail = tail.next;
if (node.next != null) {
minHeap.offer(node.next);
}
}
return dummy.next;
}
}
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}