使用最小堆合并K个有序链表：深入理解指针操作

// 链表节点定义
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) {
        // 1. 初始化最小堆
        PriorityQueue<Node> queue = new PriorityQueue<>(new NodeComparator());

        // 2. 初始化结果链表的虚拟头节点和尾指针
        Node head = new Node(0); // 虚拟头节点，其数据值不重要
        Node last = head;        // last指针初始指向head

        // 3. 将所有K个链表的头节点入堆
        for (int i = 0; i < K; i++) {
            if (arr[i] != null) {
                queue.add(arr[i]);
            }
        }

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

        // 4. 主循环：从堆中取出元素并构建结果链表
        while (!queue.isEmpty()) {
            Node curr = queue.poll(); // 取出堆顶（最小）元素

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

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

        // 5. 返回结果链表的实际头节点
        return head.next;
    }
    // ... (printList 和 main 方法省略，见完整代码)
}

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

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

return head.next;

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) {
        // Priority_queue 'queue' implemented
        // as min heap with the help of
        // 'compare' function
        PriorityQueue<Node> queue
            = new PriorityQueue<>(new NodeComparator());

        // Node at[] = new Node[K]; // 此行在原代码中未被使用，可移除
        Node head = new Node(0); // 虚拟头节点
        Node last = head;        // last指针初始指向head

        // Push the head nodes of all
        // the k lists in 'queue'
        for (int i = 0; i < K; i++) {
            if (arr[i] != null) {
                queue.add(arr[i]);
            }
        }

        // Handles the case when k = 0
        // or lists have no elements in them
        if (queue.isEmpty())
            return null;

        // Loop till 'queue' is not empty
        while (!queue.isEmpty()) {
            // Get the top element of 'queue'
            Node curr = queue.poll();

            // Add the top element of 'queue'
            // to the resultant merged list
            last.next = curr;
            last = last.next;

            // Check if there is a node
            // next to the 'top' node
            // in the list of which 'top'
            // node is a member
            if (curr.next != null) {
                // Push the next node of top node
                // in 'queue'
                queue.add(curr.next);
            }
        }
        // Address of head node of the required
        // merged list
        return head.next;
    }

    // Print linked list
    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; // K个链表

        // array to store head of linkedlist
        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(); // 输出: 0 1 2 3 4 5 6 7 8 9 10 11 
    }
}