题解 | #合并k个已排序的链表#

合并k个已排序的链表

目标

我们需要把很多条按从小到大排列的珠子串（链表）合并成一条新的珠子串，这条新的珠子串也要按从小到大的顺序排列。

示例

假设我们有三条珠子串：

• 第一条珠子串：1 → 2
• 第二条珠子串：1 → 4 → 5
• 第三条珠子串：6

我们要把这三条珠子串合并成一条新的珠子串，这条珠子串也要按从小到大的顺序排列。

解释步骤

1. 准备一个“假头”珠子

我们先在新珠子串的最前面放一个“假头”珠子，这个珠子实际上不参与最终的珠子串，但可以帮助我们更容易地开始合并。

ListNode dummy = new ListNode(0); // “假头”珠子
ListNode tail = dummy; // 用来记录新珠子串的最后一个珠子

2. 创建一个“魔法盒子”

想象一下，我们有一个“魔法盒子”，这个盒子可以自动把珠子按从小到大的顺序排好。这个“魔法盒子”其实就是一个叫做“优先队列”的工具。

PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);

3. 把每条珠子串的第一个珠子放进“魔法盒子”

我们从每条珠子串的开头开始，把每条珠子串的第一个珠子放进“魔法盒子”里。

for (ListNode list : lists) {
    if (list != null) {
        pq.add(list); // 把第一个珠子放进去
    }
}

4. 从“魔法盒子”里拿出最小的珠子

我们不断地从“魔法盒子”里拿出最小的珠子，然后把这个珠子放到新珠子串里。

while (!pq.isEmpty()) {
    // 从“魔法盒子”里拿出最小的珠子
    ListNode minNode = pq.poll();

    // 把这个珠子放到新珠子串里
    tail.next = minNode;
    tail = tail.next;

    // 如果这个珠子后面还有珠子，就把后面的珠子也放进“魔法盒子”
    if (minNode.next != null) {
        pq.add(minNode.next);
    }
}

5. 返回新珠子串的头珠子

最后，我们返回新珠子串的第一个珠子（实际上是“假头”珠子的下一个珠子）。

return dummy.next;

示例解析

假设我们有以下三条珠子串：

• 第一条珠子串：1 → 2
• 第二条珠子串：1 → 4 → 5
• 第三条珠子串：6

1. 初始化：
1. 创建“假头”珠子 dummy。
2. 创建“魔法盒子” pq。
3. 把每条珠子串的第一个珠子放进“魔法盒子”：1, 1, 6。
2. 不断从“魔法盒子”里拿出最小的珠子：
1. 取出最小珠子 1，放到新珠子串里，然后检查是否有下一个珠子，如果有则放进“魔法盒子”。
2. 再次取出最小珠子 1，放到新珠子串里，然后检查是否有下一个珠子，如果有则放进“魔法盒子”。
3. 取出最小珠子 2，放到新珠子串里，然后检查是否有下一个珠子，如果没有则继续。
4. 取出最小珠子 4，放到新珠子串里，然后检查是否有下一个珠子，如果有则放进“魔法盒子”。
5. 取出最小珠子 5，放到新珠子串里，然后检查是否有下一个珠子，如果没有则继续。
6. 取出最小珠子 6，放到新珠子串里，然后检查是否有下一个珠子，如果没有则继续。
3. 返回结果：
1. 返回合并后的珠子串的头珠子：{1, 1, 2, 4, 5, 6}。

这样，我们就得到了一条新的按从小到大排列的珠子串。

最后附上完整代码

import java.util.PriorityQueue;

public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // 创建一个优先队列，按照节点值从小到大排序
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);

        // 初始化：将所有非空链表的头节点加入优先队列
        for (ListNode list : lists) {
            if (list != null) {
                pq.add(list);
            }
        }

        // 创建虚拟头节点简化边界处理
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;

        // 只要优先队列不为空，就继续合并
        while (!pq.isEmpty()) {
            // 取出当前最小的节点
            ListNode minNode = pq.poll();
            // 将该节点加入到结果链表中
            tail.next = minNode;
            tail = tail.next;
            // 如果该节点有下一个节点，将下一个节点加入优先队列
            if (minNode.next != null) {
                pq.add(minNode.next);
            }
        }

        // 返回合并后的链表头节点
        return dummy.next;
    }
}