力扣热门100题之合并K个升序链表

核心思路超简单建一个小根堆每次能自动拿出当前最小的节点把所有链表的头结点丢进堆循环拿出最小节点接到结果链把这个节点的next再丢回堆最后返回dummy.next一句话记忆堆里存链表头每次拿最小拿完把 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) { if (lists null || lists.length 0) return null; // 小根堆按节点值从小到大排序 PriorityQueueListNode pq new PriorityQueue((a, b) - a.val - b.val); // 1. 把所有链表的头结点加入堆 for (ListNode node : lists) { if (node ! null) { pq.offer(node); } } ListNode dummy new ListNode(0); ListNode cur dummy; // 2. 依次取出最小节点再接上它的 next while (!pq.isEmpty()) { ListNode minNode pq.poll(); cur.next minNode; cur cur.next; // 把当前最小节点的下一个节点再放进堆 if (minNode.next ! null) { pq.offer(minNode.next); } } return dummy.next; } }