使用最小堆合并 K 个有序链表：原理与实现-java教程-PHP中文网

使用最小堆合并 K 个有序链表：原理与实现

本文详细介绍了如何利用最小堆高效合并 k 个已排序的链表。通过构建一个虚拟头节点和尾指针，并利用优先级队列动态维护各链表当前最小元素，逐步构建合并后的有序链表。文章将深入解析指针操作的机制，特别是`head`和`last`如何协同工作，确保合并过程的正确性，并提供完整的java代码示例及详细解释。

合并 K 个有序链表问题概述

合并 K 个有序链表是一个经典的算法问题，目标是将 K 个已经排序的链表合并成一个单一的、同样有序的链表。一个直观但效率不高的方法是两两合并，但这种方法的时间复杂度较高。更高效的解决方案是利用最小堆（优先级队列）来管理所有链表的当前最小元素。

最小堆方法的核心思想

最小堆方法的核心思想是：在任意时刻，我们只需要知道 K 个链表中所有当前未处理节点的最小值。优先级队列（Min-Heap）能够高效地提供这一功能。

初始化堆： 将 K 个链表的第一个节点（如果存在）全部加入最小堆。堆会根据节点的值进行排序，确保堆顶始终是所有节点中的最小值。
构建结果链表：
- 从堆中取出最小元素（堆顶）。
- 将该元素添加到结果链表中。
- 如果该元素所属的链表还有下一个节点，则将该下一个节点加入堆中。
重复步骤2： 直到堆为空。

通过这种方式，我们每次都能确保将当前所有链表中的最小元素添加到结果链表，从而保证最终合并链表的有序性。

关键指针操作解析：head 与 last

在构建结果链表时，通常会使用一个虚拟头节点（dummy head）和两个指针：head 和 last。理解这两个指针如何协同工作是实现此算法的关键。

Node head = new Node(0); // 虚拟头节点
Node last = head;        // last 指向当前结果链表的尾部

登录后复制

初始状态：head 和 last 都指向同一个虚拟节点，其 data 为 0，next 为 null。这个虚拟节点本身不包含任何实际数据，其作用是简化对结果链表头部的处理。

有道小P
有道小P，新一代AI全科学习助手，在学习中遇到任何问题都可以问我。

64

查看详情
```
 head  last
  ↓     ↓
┌────────────┐
│ data: 0    │
│ next: null │
└────────────┘
```
登录后复制

添加第一个实际节点： 假设从最小堆中取出的第一个最小节点是 curr (例如 data: 42)。执行 last.next = curr; 这行代码将 last 指向的节点的 next 字段设置为 curr。由于 head 和 last 最初指向同一个节点，因此 head 指向的节点的 next 字段也被更新了。

 head  last          curr
  ↓     ↓             ↓
┌────────────┐    ┌────────────┐
│ data: 0    │    │ data: 42   │
│ next: ─────────►│ next: null │
└────────────┘    └────────────┘

登录后复制

接着执行 last = last.next; 这行代码将 last 指针向前移动，使其指向刚刚添加到链表中的新节点 curr。此时，head 仍然指向虚拟头节点，而 last 已经指向了结果链表的第一个实际节点。

 head              last curr
  ↓                 ↓    ↓
┌────────────┐    ┌────────────┐
│ data: 0    │    │ data: 42   │
│ next: ─────────►│ next: null │
└────────────┘    └────────────┘

登录后复制

后续节点添加： 当循环继续，从堆中取出下一个最小节点 curr (例如 data: 50)。执行 last.next = curr; 此时 last 指向的是 data: 42 的节点。这行代码将 data: 42 节点的 next 字段设置为 data: 50 的节点。

 head                               last curr
  ↓                                  ↓    ↓
┌────────────┐    ┌────────────┐    ┌────────────┐
│ data: 0    │    │ data: 42   │    │ data: 50   │
│ next: ─────────►│ next: ─────────►│ next: null │
└────────────┘    └────────────┘    └────────────┘

登录后复制

执行 last = last.next;last 指针再次向前移动，指向 data: 50 的节点。

 head                                        last curr
  ↓                                           ↓    ↓
┌────────────┐    ┌────────────┐    ┌────────────┐
│ data: 0    │    │ data: 42   │    │ data: 50   │
│ next: ─────────►│ next: ─────────►│ next: null │
└────────────┘    └────────────┘    └────────────┘

登录后复制

整个过程中，head 始终保持指向最初的虚拟头节点。通过 head 我们可以访问到整个合并后的链表，而 last 则负责不断地在链表末尾追加新节点。最终，我们需要返回 head.next，因为虚拟头节点本身不包含有效数据。

Java 代码实现

以下是使用 Java 实现合并 K 个有序链表的完整代码示例。

import java.util.Comparator;
import java.util.PriorityQueue;

// 链表节点定义
class Node {
    int data;
    Node next;

    Node(int key) {
        data = key;
        next = null;
    }
}

// 节点比较器，用于最小堆
class NodeComparator implements Comparator<Node> {
    @Override
    public int compare(Node k1, Node k2) {
        return Integer.compare(k1.data, k2.data); // 简化比较逻辑
    }
}

class Solution {
    /**
     * 合并 K 个有序链表
     * @param arr 包含 K 个链表头节点的数组
     * @param K 链表的数量
     * @return 合并后的有序链表的头节点
     */
    public static Node mergeKList(Node[] arr, int K) {
        // 使用优先级队列作为最小堆，并传入自定义比较器
        PriorityQueue<Node> queue = new PriorityQueue<>(new NodeComparator());

        // 创建一个虚拟头节点，简化结果链表的构建
        Node head = new Node(0);
        Node last = head; // last 指向当前结果链表的尾部

        // 将所有 K 个链表的第一个节点（如果存在）加入最小堆
        for (int i = 0; i < K; i++) {
            if (arr[i] != null) {
                queue.add(arr[i]);
            }
        }

        // 处理 K=0 或所有链表为空的情况
        if (queue.isEmpty()) {
            return null;
        }

        // 当堆不为空时，循环执行以下操作
        while (!queue.isEmpty()) {
            // 从堆中取出当前最小的节点
            Node curr = queue.poll();

            // 将取出的节点添加到结果链表的尾部
            last.next = curr;
            last = last.next; // 移动 last 指针到新添加的节点

            // 如果当前节点所属的链表还有后续节点，则将其加入堆中
            if (curr.next != null) {
                queue.add(curr.next);
            }
        }

        // 返回虚拟头节点的下一个节点，即合并后链表的实际头节点
        return head.next;
    }

    // 打印链表
    public static void printList(Node node) {
        while (node != null) {
            System.out.print(node.data + " ");
            node = node.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int N = 3;

        // 创建 K 个链表
        Node[] a = new Node[N];

        // 链表1: 1 -> 3 -> 5 -> 7
        Node head1 = new Node(1);
        a[0] = head1;
        head1.next = new Node(3);
        head1.next.next = new Node(5);
        head1.next.next.next = new Node(7);

        // 链表2: 2 -> 4 -> 6 -> 8
        Node head2 = new Node(2);
        a[1] = head2;
        head2.next = new Node(4);
        head2.next.next = new Node(6);
        head2.next.next.next = new Node(8);

        // 链表3: 0 -> 9 -> 10 -> 11
        Node head3 = new Node(0);
        a[2] = head3;
        head3.next = new Node(9);
        head3.next.next = new Node(10);
        head3.next.next.next = new Node(11);

        // 合并链表并打印结果
        Node res = mergeKList(a, N);
        if (res != null) {
            System.out.print("合并后的链表: ");
            printList(res); // 预期输出: 0 1 2 3 4 5 6 7 8 9 10 11
        } else {
            System.out.println("合并结果为空链表。");
        }
    }
}

登录后复制

代码详解

Node 类： 定义了链表节点的基本结构，包含一个整型数据 data 和指向下一个节点的 next 指针。
NodeComparator 类： 实现了 Comparator<Node> 接口，用于自定义 Node 对象在 PriorityQueue 中的比较规则。这里是根据 data 字段进行升序比较，确保这是一个最小堆。
mergeKList(Node[] arr, int K) 方法：
- PriorityQueue<Node> queue = new PriorityQueue<>(new NodeComparator());：创建了一个优先级队列，它将作为我们的最小堆。
- Node head = new Node(0); Node last = head;：初始化虚拟头节点 head 和尾指针 last。
- for (int i = 0; i < K; i++) { if (arr[i] != null) { queue.add(arr[i]); } }：遍历输入链表数组，将每个链表的第一个节点（如果非空）添加到最小堆中。
- while (!queue.isEmpty()) { ... }：主循环，只要堆不为空，就继续处理。
  - Node curr = queue.poll();：从堆中取出当前所有链表头节点中的最小值。
  - last.next = curr;：将取出的节点 curr 连接到结果链表的末尾。
  - last = last.next;：将 last 指针移动到刚刚添加的 curr 节点，使其始终指向结果链表的当前尾部。
  - if (curr.next != null) { queue.add(curr.next); }：如果 curr 节点所属的链表还有下一个节点，则将该下一个节点加入堆中，以便在后续迭代中进行比较。
- return head.next;：返回合并后链表的实际头节点（跳过虚拟头节点）。
printList 和 main 方法： 用于辅助打印链表和演示如何使用 mergeKList 方法。

时间与空间复杂度

时间复杂度： 假设所有链表的总节点数为 N，每个链表平均有 N/K 个节点。堆中最多同时存在 K 个节点。
- 初始化：K 次 add 操作，每次 O(logK)。总计 O(K logK)。
- 主循环：N 次 poll 操作和最多 N 次 add 操作，每次 O(logK)。总计 O(N logK)。
- 因此，总时间复杂度为 O(N logK)。
空间复杂度： 优先级队列中最多存储 K 个节点，因此空间复杂度为 O(K)。