当前位置：首页 > news >正文

【CT】LeetCode手撕—23. 合并 K 个升序链表

news 来源：原创 2024/9/29 7:17:53

题目

原题连接：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;}}
}