题目:
给你一个链表数组,每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中,返回合并后的链表。
示例 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;}
}