克隆一个链表，其中每个节点都有一个指向链表中任何其他节点的随机指针

Question

请帮助我查找代码中的错误(1( 。

您将得到一个包含N个节点的Singly Linked List，其中每个节点下一个都指向其下一个节点。你还得到了M个随机指针，其中你将得到M个对，表示两个节点a和b，即a->arb=b.

任务是完成函数copyList((，该函数使用一个参数作为要克隆的链表的头，并应返回克隆的链表头。注意：如果它们是未给定任意指针的任何节点，则默认为null。

我试图为上述问题编写代码。。但不起作用

// { Driver Code Starts
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node *next;
Node *arb;
Node(int x) {
data = x;
next = NULL;
arb = NULL;
}
};
void print(Node *root) {
Node *temp = root;
while (temp != NULL) {
int k;
if (temp->arb == NULL)
k = -1;
else
k = temp->arb->data;
cout << temp->data << " " << k << " ";
temp = temp->next;
}
}
Node *copyList(Node *head);
void append(Node **head_ref, Node **tail_ref, int new_data) {
Node *new_node = new Node(new_data);
if (*head_ref == NULL) {
*head_ref = new_node;
} else
(*tail_ref)->next = new_node;
*tail_ref = new_node;
}
bool validation(Node *head, Node *res, Node *cloned_addr,
Node *generated_addr) {
if (generated_addr == cloned_addr) return false;
Node *temp1 = head;
Node *temp2 = res;
int len1 = 0, len2 = 0;
while (temp1 != NULL) {
len1++;
temp1 = temp1->next;
}
while (temp2 != NULL) {
len2++;
temp2 = temp2->next;
}
/*if lengths not equal */
if (len1 != len2) return false;
temp1 = head;
temp2 = res;
while (temp1 != NULL) {
if (temp1->data != temp2->data) return false;
if (temp1->arb != NULL and temp2->arb != NULL) {
if (temp1->arb->data != temp2->arb->data) return false;
} else if (temp1->arb != NULL and temp2->arb == NULL)
return false;
else if (temp1->arb == NULL and temp2->arb != NULL)
return false;
temp1 = temp1->next;
temp2 = temp2->next;
}
return true;
}
/* Driver program to test above function*/
int main() {
int T, i, n, l, k;
Node *generated_addr = NULL;
/*reading input stuff*/
cin >> T;
while (T--) {
generated_addr = NULL;
struct Node *head = NULL, *tail = NULL;
cin >> n >> k;
for (i = 1; i <= n; i++) {
cin >> l;
append(&head, &tail, l);
}
for (int i = 0; i < k; i++) {
int a, b;
cin >> a >> b;
Node *tempA = head;
int count = -1;
while (tempA != NULL) {
count++;
if (count == a - 1) break;
tempA = tempA->next;
}
Node *tempB = head;
count = -1;
while (tempB != NULL) {
count++;
if (count == b - 1) break;
tempB = tempB->next;
}
// when both a is greater than N
if (a <= n) tempA->arb = tempB;
}
/*read finished*/
generated_addr = head;
Node *res = copyList(head);
Node *cloned_addr = res;
cout << validation(head, res, cloned_addr, generated_addr) << endl;
}
return 0;
}
// } Driver Code Ends

/*  the node structure is as follows
struct Node {
int data;
Node *next;
Node *arb;
Node(int x) {
data = x;
next = NULL;
arb = NULL;
}
};
*/
// Should return the head of the copied linked list the
// output will be 1 if successfully copied
Node *copyList(Node *head) {
if(!head)
return nullptr;

Node*q=head;
Node*clone=new Node(q->data);
clone->next=0;
clone->arb=q->arb;
Node*p=clone;
Node*r=q;
q=q->next;
while(q)
{
r->next=p;
p->next=new Node(q->data);
p=p->next;
p->next=0;
p->arb=q->arb;
r=q;
q=q->next;
}
r->next=p;
p=clone;
while(p)
{
if(p->arb)
p->arb=p->arb->next;
p=p->next;
}

return clone;

}

Answer 1

在构建克隆列表之前，无法分配列表中的指针，因为在此之前，要指向的节点将不存在。

因此，您需要两次迭代：第一次是克隆列表并创建一个将原始节点与克隆相关联的字典，第二次是更新指针。代码如下所示：

Node *copyList(Node *head) {
if(!head)
return nullptr;

Node* it1 = head;
Node* clone = new Node;
Node* it2 = clone;

std::map<Node*, Node*> nodeDict;
nodeDict[nullptr] = nullptr;

// first iteration: create the list and the values
while(it1){
it2->data = it1->data;
nodeDict[it1] = it2;

it1 = it1->next;
it2->next = it1 ? new Node: nullptr;
it2 = it2->next;
}
// second iteration: connect the nodes
it1 = head;
it2 = clone;
while(it1){
it2->arb = nodeDict[it1->arb];
it1 = it1->next;
it2 = it2->next;
}

return clone;
}