基于最小堆合并K个有序链表：head节点赋值逻辑疑问

这段用最小堆（PriorityQueue）实现K个有序链表合并的Java代码里，初始化了head和last两个节点引用，全程只对last做赋值和属性修改，但最终head却能关联到完整的合并链表，核心原因是Java对象引用的特性，下面拆解逻辑：

核心逻辑拆解 #

1. 初始阶段：Node head = new Node(0); Node last = head;
   这里head和last是指向同一个Node对象的引用（这个对象是个哨兵节点，用来简化链表操作，避免处理空链表的边界情况）。此时head和last都指向这个哨兵节点，修改其中一个的属性，另一个能看到变化。

2. 第一次循环操作：

   • last.next = curr：这一步是修改了哨兵节点的next属性，把堆中取出的最小节点curr挂到哨兵节点后面。因为head指向的就是这个哨兵节点，所以head.next现在也指向curr了。
   • last = last.next：这一步是让last引用从哨兵节点，移动到刚添加的curr节点上，准备下次在链表末尾添加新节点。

3. 后续循环重复过程：
   每次循环都把堆里取出的最小节点挂到当前last的next上（也就是链表的最后一个节点后面），然后把last移动到新添加的节点。而head始终指向最初的哨兵节点，哨兵节点的next就是合并链表的第一个节点，后面跟着所有依次添加的节点，自然就能通过head.next拿到完整的合并链表。

完整代码 #

// Java code for the above approach

class Node {
    int data;
    Node next;

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

// Class implements Comparator to compare Node data
class NodeComparator implements Comparator<Node> {

    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;
        // 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;
    
        // array to store head of linkedlist
        Node[] a = new Node[N];
    
        // Linkedlist1
        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);
    
        // Limkedlist2
        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
        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();
    }
}

内容的提问来源于stack exchange，提问作者The Ack