[LeetCode Hot 100] LeetCode23. 合并K个升序链表

题目描述

思路：优先队列

使用优先队列这个数据结构，对于这个数据结构，我们不用去管内部是如何实现的，我们只要知道有这么一种数据结构能帮助我们将一堆数据塞到优先队列这一个黑盒中，然后我们可以获取这堆数中最小的值或者最大的值。

代码一：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null;
        // 虚拟头节点
        ListNode dummy = new ListNode();
        ListNode p = dummy;
        // 优先队列 底层数据结构是小顶堆
        PriorityQueue<ListNode> pq = new PriorityQueue<>(lists.length, (a, b) -> (a.val - b.val));

        // 将K个链表的头节点加入优先队列中
        for (ListNode head : lists) {
            if (head != null) {
                pq.add(head);
            }
        } 

        while (!pq.isEmpty()) {
            // 获取最小节点,接到结果链表中
            ListNode node = pq.poll();
            p.next = node;
            if (node.next != null) {
                pq.add(node.next);
            }
            // p指针不断前进
            p = p.next;
        }
        return dummy.next;
    }
}