2025年- H97-Lc205--23.合并k个升序链表(链表、小根堆、优先队列）--Java版

1.题目描述

2.思路

2个链表的合并
分别使用两个指针，指向2个链表的头结点，每次取出值较小的节点，并把对应的指针后移，直到2个链表便利完成。

4个链表的合并
初始4个指针都指向每个链表头结点，每次遍历这4个节点，找到最小的那个节点加入到结果，然后对应指针后移。

如果有n个链表，每次遍历k个节点，时间复杂度就是O（nk），k个节点的优化就是采用小根堆。用小根堆存储k个节点，每次弹出堆顶元素，下一个节点加入堆中，加入的时间复杂度是O(logK)
所以此时的时间复杂度是O（nlogk）

（1）自定义比较函数
（2）把每个链表的头结点加入堆中
（3）定义虚拟头结点，当前指针指向头结点
（4）当堆不空的时候，弹出堆顶元素。同时把节点插入到当起啊指针的下一个节点，当前指针后移
（5）如果当前节点存在下一个节点，把它插入到堆中
（6）返回头结点

例子：

3.代码实现

/**
 * 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) {
        //1.定义小根堆，按照节点升序排序。
        PriorityQueue<ListNode> heap=new PriorityQueue<>(
            (a,b)->a.val-b.val
        );

        //2.把每个链表的头结点加入到堆中
        for(ListNode node :lists)
        {
            if(node!= null)
            {
                heap.offer(node);
            }
        }
        //3.定义虚拟头结点
        ListNode dummyhead=new ListNode(0);
        ListNode cur=dummyhead;

        //4.当堆不空的时候，弹出堆顶最小结点，加入结果链表
        while(!heap.isEmpty())
        {
            ListNode node=heap.poll();//弹出最小哦结点
            cur.next=node;//加入结果链表;
            //移动当前指针
            cur=cur.next;
            //如果结点还有下一个节点，把它加入堆
            if(node.next!=null)
            {
                heap.offer(node.next);
            }
        }
        //6.返回合并后的头结点的下一个节点，虚拟头结点是0
        return dummyhead.next;
        
  
    }
}