今天是秋招算法打卡第三天，题目是合并k个已排序的链表

问题：合并k个已排序的链表

描述：

合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。

数据范围：节点总数满足 0≤n≤10^5，链表个数满足 1≤k≤10^5  ，每个链表的长度满足 1 ≤len≤200  ，每个节点的值满足 |val| <= 1000

要求：时间复杂度 O(nlogk)

解题方法

1、优先队列（小顶堆）

1）每次取出所有链表的当前头节点，加入优先队列，使用小顶堆进行排序

2）取出当前小顶堆中堆顶元素，将该节点的下一个节点加入小顶堆

3）依次循环，直到所有链表的节点都并入新链表，即小顶堆为空

import java.util.*;
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        //小顶堆 ps：牛客中必须实现小顶堆的定义，无法使用Java中默认的小顶堆
        Queue<ListNode> pq = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);
        //将链表的头节点加入到小顶堆中
        for(int i = 0; i < lists.size(); i++){
            //获取每一个链表
            ListNode tmp1 = lists.get(i);
            //当头节点不为null时，加入小顶堆
            if(tmp1 != null){
                pq.add(tmp1);
            }
        }
        //虚拟头节点
        ListNode dummy = new ListNode(-1);
        ListNode index = dummy;
        //当小顶堆不为null时，即内部还存在节点时，依次将堆顶元素弹出，并入新链表
        while(!pq.isEmpty()){
            //弹出并返回堆顶元素
            ListNode tmp2 = pq.poll();
            //将该节点并入新链表
            index.next = tmp2;
            index = index.next;
            //当该节点所在的链表还有剩余节点时，将该节点的下一节点加入小顶堆
            tmp2 = tmp2.next;
            if(tmp2 != null){
                pq.add(tmp2);
            }
        }
        //小顶堆为null，所有链表的节点都并入新链表
        return dummy.next;
    }
}