题目

• 原题连接：23. 合并 K 个升序链表

---

1- 思路

• 模式识别：合并 K 个链表 ——> 优先队列

思路

• 借助优先队列，每次从 k 个链表中，各取一个元素，添加到优先队列中。
• 保证优先队列中 只有 k 个元素

---

2- 实现

⭐23. 合并 K 个升序链表——题解思路

class Solution {public ListNode mergeKLists(ListNode[] lists) {int len = lists.length;if(len == 0){return null;}PriorityQueue<ListNode> pq = new PriorityQueue<>(len, Comparator.comparingInt(a -> a.val));ListNode dummyHead = new ListNode(-1);ListNode curNode = dummyHead;for(ListNode list : lists){// 将每个 list 的头结点加入if(list!=null){pq.add(list);}}// 处理链表排序逻辑while(!pq.isEmpty()){ListNode node = pq.poll();curNode.next = node;curNode = curNode.next;if(curNode.next!=null){pq.add(curNode.next);}}return dummyHead.next;}
}

---

3- ACM 实现

public class mergeK {static class ListNode{int val;ListNode next;ListNode(){}ListNode(int x){val =x;}}public static ListNode mergeK(ListNode[] lists){int len = lists.length;if(len==0){return null;}// 1. 数据结构PriorityQueue<ListNode> pq = new PriorityQueue<>(len, Comparator.comparingInt(a -> a.val));ListNode dummyHead = new ListNode(-1);ListNode cur = dummyHead;// 2. 头入队for(ListNode list:lists){if(list!=null){pq.add(list);}}//3.排序逻辑while(!pq.isEmpty()){ListNode node = pq.poll();cur.next = node;cur = cur.next;if(cur.next!=null){pq.add(cur.next);}}return dummyHead.next;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("输入链表的个数 k ");int k = sc.nextInt();ListNode[] lists = new ListNode[k];for(int i = 0 ; i < k ; i++){ListNode dummyHead = new ListNode(0);ListNode cur = dummyHead;System.out.println("输入第"+(i+1)+"个链表的元素个数");int n  = sc.nextInt();System.out.println("输入元素");for(int j = 0 ; j < n ;j++){cur.next = new ListNode(sc.nextInt());cur = cur.next;}lists[i] = dummyHead.next;}ListNode forRes = mergeK(lists);while(forRes!=null){System.out.print(forRes.val + " ");forRes = forRes.next;}}
}