How the head is getting populated in below code of merging k sorted lists with min heap

Question

The code is below uses a min heap along side linked list to store and manipulate. Here priority queue is being used and head is referenced to tail, but every time even though head is not populating value of last is being populated. The confusion is that the way last value is being populated in head.

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

I tried to debug this, but I really was not able to understand how is head being populated every time last is changing.

Answer 1

how is head being populated everytime last is changing.

First we have this initialisation:

Node head = new Node(0);
Node last = head;

That means both variables reference the same (dummy) node. We can represent that as follows:

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

Then queue is populated with references to nodes. In the while loop we get this:

Node curr = queue.poll();

So curr references some node, let's say with value 42. We can imagine the state as follows:

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

Then we get to the crucial step:

last.next = curr;

This establishes the link to the curr node:

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

Note how this mutates the left node, which also head is referencing -- so it does influence what we see via head.

And to complete this step, last is made to reference the newly appended node:

last = last.next;

Which can be pictured like this:

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

If the loop repeats, then more nodes will be added, so the list may evolve to something like this:

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

I hope this clarifies it.