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

// 链表节点定义
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) {
        if (k1.data > k2.data)
            return 1;
        else if (k1.data < k2.data)
            return -1;
        return 0;
    }
}

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) {
        if (k1.data > k2.data)
            return 1;
        else if (k1.data < k2.data)
            return -1;
        return 0;
    }
}

class GFG {
    // Function to merge k sorted linked lists
    static Node mergeKList(Node[] arr, int K) {
        // 使用NodeComparator创建最小堆
        PriorityQueue<Node> queue = new PriorityQueue<>(new NodeComparator());

        // 创建一个虚拟头节点（dummy head）
        Node head = new Node(0);
        // last指针指向当前结果链表的末尾，初始时与head指向同一个虚拟节点
        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;

        // 示例：创建3个有序链表
        Node[] a = new Node[N];

        // Linkedlist1: 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);

        // Linkedlist2: 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);

        // Linkedlist3: 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();
    }
}

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

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