题解 | #牛群的合并#

知识点：链表

我们需要合并多个链表，使其升序排列，一个有效的方法将所有的节点放入堆中，遍历完所有节点，同时将节点的后继指针指向空，最后在依次从堆顶拿出最小的节点，组合成新的链表。需要注意的是，在Java中使用PriorityQueue优先级队列来实现堆，我们也需要重写堆的比较方法，使其按照节点的val值升序排列。

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
        PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>((o1, o2) -> (o1.val - o2.val));
        for(ListNode node: lists) {
            while(node != null) {
                ListNode tmp = node.next;
                node.next = null;
                heap.offer(node);
                node = tmp;
            }
        }
        ListNode preHead = new ListNode(-1);
        ListNode node = preHead;
        while(!heap.isEmpty()) {
            node.next = heap.poll();
            node = node.next;
        }
        return preHead.next;
    }
}