合并k个升序链表：小顶堆

题目

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

思考

这道题需要什么？我们先从暴力法看看

import java.util.*;

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        List<Integer> list = new ArrayList<>();
//遍历，非空添加进来
        for (ListNode head : lists) {
            ListNode curr = head;
            while (curr != null) {
                list.add(curr.val);
                curr = curr.next;
            }
        }
//排序

        Collections.sort(list);

//        虚拟头节点拿值
        ListNode dummy = new ListNode(-1);
        ListNode curr = dummy;
        for (int i : list) {
            curr.next = new ListNode(i);
            curr = curr.next;
        }
        return dummy.next;
    }
}

也是非常的暴力呢！直接全部拿出来一起排序再塞回去，我们会发现这样子不需要题目的升序了，怎么利用升序条件呢？堆栈就出来了，让我们看看代码

import java.util.PriorityQueue;

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // 1. 初始化小顶堆，按节点值升序排列
        PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> a.val - b.val);

        // 2. 把所有非空链表的头节点入堆
        for (ListNode head : lists) {
            if (head != null) {
                heap.offer(head);
            }
        }

        // 3. 哑节点构建结果链表
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;

        // 4. 循环取最小节点
        while (!heap.isEmpty()) {
            // 弹出当前最小节点
            ListNode minNode = heap.poll();
            // 拼到结果链表
            cur.next = minNode;
            cur = cur.next;

            // 如果这条链表还有后续节点，把下一个节点入堆
            if (minNode.next != null) {
                heap.offer(minNode.next);
            }
        }

        return dummy.next;
    }
}

‍