如何在下面的代码中填充k个排序列表和最小堆

Question

下面的代码使用最小堆和边链表来存储和操作。这里使用的是优先级队列，并且head被引用到tail，但每次即使head没有填充，也会填充last的值。令人困惑的是最后的方式头部.

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

我试着调试这个，但我真的不能理解是如何头每次最后被填充正在改变。

Answer 1

每次last变化时head是如何被填充的

首先我们有这样的初始化:

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

这意味着两个变量都引用了相同的(虚拟)节点。我们可以这样表示:

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

则用节点引用填充queue。在while循环中，我们得到这个:

Node curr = queue.poll();

所以curr引用了某个节点，假设值为42。我们可以想象如下的状态:

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

然后我们进入关键的一步:

last.next = curr;

建立到curr节点的链接:

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

注意这是如何改变左节点的，这也是head引用的——所以它确实影响了我们通过head看到的。

为了完成这一步，last引用新附加的节点:

last = last.next;

可以如下图所示:

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

如果循环重复，则会添加更多节点，因此列表可能演变为如下所示:

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

我希望这能说清楚。