题解 | #牛群的合并#

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
        // 创建结果链表的虚拟头节点
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy; // 当前节点

        // 创建最小堆，用于维护所有牛群的头节点
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);

        // 将所有牛群的头节点加入最小堆
        for (ListNode groupHead : lists) {
            if (groupHead != null) {
                minHeap.offer(groupHead);
            }
        }

        // 逐步从最小堆中取出最小头节点，合并到结果链表中
        while (!minHeap.isEmpty()) {
            ListNode minNode = minHeap.poll(); // 取出最小头节点
            cur.next = minNode; // 将节点加入结果链表
            cur = cur.next; // 移动指针

            // 将取出节点的下一个节点加入最小堆
            if (minNode.next != null) {
                minHeap.offer(minNode.next);
            }
        }

        return dummy.next; // 返回结果链表的头节点
    }
}

题目考察的知识点：

合并有序链表。

解题方法分析：

1. 创建一个新的链表作为结果链表，初始化为一个空节点。
2. 使用一个优先队列（最小堆）来维护所有牛群的当前头节点，以便按照升序合并。
3. 遍历所有牛群，将每个牛群的头节点加入到优先队列中。
4. 从优先队列中取出最小的头节点，将其加入到结果链表中，并将该头节点的下一个节点（如果存在）加入到优先队列中。
5. 重复步骤 4，直到优先队列为空。
6. 返回结果链表的头节点的下一个节点，即为合并后的大牛群。