Java 题解 | #牛群的合并#

本题考察的知识点包括：链表的基本数据结构、（我这个代码还用到了优先队列），因为每个链表都是排序的，按照升序排序还是很简单的。

如果想写其他的解法，感觉可以考虑指针。

解决方案通过使用优先队列（最小堆）来管理所有链表的节点。首先，我们将每个链表的头节点添加到优先队列中。每次从优先队列中取出最小的节点，并将其添加到合并后链表中。然后，如果被取出的节点有下一个节点，则将下一个节点添加回优先队列中。重复这个过程，直到优先队列为空。最后，返回合并后链表的头节点。

1. 检查输入参数 lists 是否为 null 或者空数组。如果是，则返回 null，因为没有需要合并的链表。
2. 创建一个优先队列（最小堆） minHeap 来存储链表的节点。我们将使用 Comparator.comparingInt 方法传入一个lambda 函数，以便根据节点的值进行比较。
3. 使用 for 循环遍历 lists 数组的每个链表，并将链表的头节点添加到优先队列 minHeap 中。注意，在添加之前，需要先检查当前链表是否为空。
4. 创建一个哑节点 dummy 作为合并后链表的头节点，同时创建一个指针 curr 指向当前节点，初始时指向 dummy 节点。
5. 进入一个循环，当优先队列 minHeap 不为空时，执行以下操作：

使用 minHeap.poll() 方法取出最小的节点 smallest。

将 smallest 节点连接到合并后链表中，即 curr.next = smallest。

更新 curr 指针，让其指向刚刚插入的节点，即 curr = curr.next。

检查 smallest 节点是否还有下一个节点，如果有，则将其添加回优先队列 minHeap 中，即 minHeap.offer(smallest.next)。

6. 当循环结束时，所有的链表都已经合并到了合并后的链表中。返回哑节点 dummy 的下一个节点作为合并后链表的头节点。

这个解决方案的时间复杂度是 O(N log K)，其中 N 是所有链表中节点的总数，K 是链表的数量。每次从优先队列中取出最小值的操作的时间复杂度是 log K，该操作最多执行 N 次

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param lists ListNode类一维数组 
     * @return ListNode类
     */
    public ListNode mergeKLists (ListNode[] lists) {
        // write code here
          if (lists == null || lists.length == 0) {
            return null;
        }
        
        // 使用优先队列（最小堆）来存储链表节点
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>(Comparator.comparingInt(node -> node.val));
        
        // 初始化优先队列，将每个链表的头节点加入队列中
        for (ListNode list : lists) {
            if (list != null) {
                minHeap.offer(list);
            }
        }
        
        // 创建一个哑节点作为合并后链表的头节点
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        
        // 从优先队列中取出最小的节点，并将其下一个节点添加到队列中
        while (!minHeap.isEmpty()) {
            ListNode smallest = minHeap.poll();
            curr.next = smallest;
            curr = curr.next;
            
            if (smallest.next != null) {
                minHeap.offer(smallest.next);
            }
        }
        
        return dummy.next;
        
    }
}