题解 | #牛群的合并#

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;
	  	// 定义一个堆(优先队列)，并定义比较器规则 -> 按节点值升序 -> 小顶堆
        Queue<ListNode> queue = new PriorityQueue<>((o1, o2) -> o1.val - o2.val);
	  	// 遍历节点数组，将节点加入到优先队列中
        for (ListNode node : lists) {
		  	// !!! 注意: 这里需要判断边界值，空链表跳过
            if (node != null) queue.offer(node);
        } 
	  	// 定义返回结果的头节点，和一个cur: 用于将遍历过程中的各个节点串联起来
        ListNode head = null, cur = null;
	  	// 只要堆中还有元素，就一直遍历
        while (!queue.isEmpty()) {
		  	// 堆中弹出一个节点
            ListNode node = queue.poll();
		  	// 如果头节点为空，即还没设置，就设置头节点，并将cur指向头节点
            if (head == null) {
			  	// 只会第一次进来
                head = node;
                cur = head;
            } else {
			  	// 否则，将新弹出的节点，接到链表后面
                cur.next = node;
            }
		  	// cur往后走一步
            cur = node;
		  	// 如果node还有下一个节点，就将下一个节点加入到优先队列中
            if (node.next != null) queue.offer(node.next);
        }
	  	// 返回头节点
        return head;
    }
}