使用最小堆高效合并K个有序链表：Java实现与指针机制解析

class Node {
    int data;
    Node next;

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

import java.util.Comparator;
import java.util.PriorityQueue; // 导入PriorityQueue

class NodeComparator implements Comparator<Node> {
    @Override
    public int compare(Node k1, Node k2) {
        if (k1.data > k2.data)
            return 1; // k1 大于 k2
        else if (k1.data < k2.data)
            return -1; // k1 小于 k2
        return 0; // k1 等于 k2
    }
}

class GFG {
    static Node mergeKList(Node[] arr, int K) {
        // 使用自定义比较器初始化最小优先队列
        PriorityQueue<Node> queue = new PriorityQueue<>(new NodeComparator());

        // 创建一个虚拟头节点（dummy head），用于简化链表操作
        Node head = new Node(0);
        // last指针将始终指向当前结果链表的尾部
        Node last = head;

        // 将所有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();

            // 将curr节点添加到结果链表的尾部
            last.next = curr;
            // 更新last指针，使其指向新添加的节点
            last = last.next;

            // 如果curr节点所属的链表还有后续节点，则将其下一个节点加入优先队列
            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;
        }
    }

    // 主函数示例
    public static void main(String[] args) {
        int N = 3;
        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)
            printList(res);
        System.out.println(); // 输出结果：0 1 2 3 4 5 6 7 8 9 10 11
    }
}

Node head = new Node(0); // 虚拟头节点
Node last = head;        // last指针初始指向虚拟头节点