题解 | #牛群的合并# java

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<>((a, b) -> a.val - b.val);
        // 将所有链表的头节点加入最小堆
        for (ListNode node : lists) {
            if (node != null) {
                minHeap.offer(node);
            }
        }

        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        // 不断从最小堆中取出当前最小的节点，将其接到结果链表中，并将下一个节点加入最小堆
        while (!minHeap.isEmpty()) {
            ListNode node = minHeap.poll();
            curr.next = node;
            curr = curr.next;
            if (node.next != null) {
                minHeap.offer(node.next);
            }
        }

        return dummy.next;
    }
    }

首先，创建一个最小堆（PriorityQueue），指定比较器为根据节点值的升序排列。

然后，遍历输入的链表数组，将每个链表的头节点加入最小堆。注意，在添加之前需要判断节点是否为空。

创建一个虚拟头节点 dummy 和一个指针 curr，用于构建合并后的结果链表。开始循环，不断从最小堆中取出当前最小的节点，将其接到结果链表的尾部，并将 curr 指向新加入的节点。同时，如果当前节点还有下一个节点，将其加入最小堆。

返回 dummy.next，即合并后的链表头节点。

该题考察的知识点是合并 k 个有序链表。

解题思路是使用最小堆（PriorityQueue）来实现合并。首先将所有链表的头节点加入最小堆中，然后从最小堆中取出当前最小的节点，将其接到结果链表中，并将下一个节点加入最小堆。重复这个过程直到最小堆为空。