【LeetCode】【算法】23. 合并K个升序链表

LeetCode 23. 合并K个升序链表

题目描述

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

思路

思路：用小根堆解，很强

1. 创建一个小根堆，排序规则为小根堆排序规则new PriorityQueue<>((v1,v2) -> v1.val-v2.val);
2. 将lists中的所有节点都放到这个小根堆里去，pq.offer(node)为将节点放入小根堆
3. 当小根堆不为空时，不断获取小根堆最小值pq.poll()，并将该值链接到我们定义的dummyListNode后面去；若最小值minNode.next!=null，则继续将最小值放入小根堆pq.offer(minNode.next)

代码

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode mergeKLists(ListNode[] lists) {// 小根堆排大小PriorityQueue<ListNode> pq = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);for (ListNode node : lists) {if (node != null) {pq.offer(node);}}ListNode dummyHead = new ListNode(0), cur = dummyHead;while (!pq.isEmpty()) {ListNode minNode = pq.poll();cur.next = minNode;cur = minNode;if (minNode.next != null) {pq.offer(minNode.next);}}return dummyHead.next;}
}