我在克隆链表时遇到问题，我的代码有什么问题？

Question

Node 的结构：

class Node{
    public:
    int data;
    Node *next;
    Node *arb;
    Node(int value){
        data=value;
        next=NULL;
        arb=NULL;
    }
};

现在，我编写了以下代码，但出现了分段错误 运行时错误。我找不到导致此错误的原因。

Node *copyList(Node *head)
    {
        Node* ptr=head;
        Node *temp;
        Node *clonehead; 
        Node *clonetail;
        while(ptr!=NULL){
            temp=ptr->next;
            Node* newnode=new Node(ptr->data);
            if(ptr==head){
                clonehead=newnode;
                clonetail=clonehead;
            }
            else{
                clonetail->next=newnode;
                clonetail=newnode;
            }
            clonetail->arb=ptr->arb;
            ptr->next=clonetail;
            ptr=temp;
        }
        ptr=clonehead;
        while(ptr!=NULL){
            temp=ptr->arb;
            ptr->arb=temp->next;
            ptr=ptr->next;
        }
        return clonehead;
    }

我的代码有什么问题？

Link 问题：Clone a linked list with next and random pointer

Answer 1

你的代码有几个错误：

clonetail->arb=ptr->arb;

您提供的说明非常清楚，克隆列表中的next和arb指针需要指向克隆列表中的节点，而不是原始列表中的节点。
ptr->next=clonetail;

您正在修改原始列表中节点的 next 指针，您根本不应该这样做。
这段代码毫无意义：
```
while(ptr!=NULL){
    temp=ptr->arb;
    ptr->arb=temp->next;
    ptr=ptr->next;
}
```
您正在遍历克隆列表，并且对于每个 arb（指向原始列表中的节点，而不是克隆列表中的节点），您正在更新它以指向引用节点的next 节点而不是引用节点本身。您没有考虑 arb 可能为 NULL 的可能性，或者克隆的 arb 指向错误列表中的节点的事实。

由于每个节点的 arb 指向同一列表中的随机节点，因此您无法在克隆节点的同一循环中克隆 arb，因为任何给定的 arb 可能指的是尚未克隆的较新节点。

要克隆 arbs，您必须首先完成从原始列表中克隆节点，然后遍历克隆列表更新其 arbs 以指向正确的节点在克隆列表中，而不是原始列表中。我相信这就是您试图要做的事情，但您做的不正确。

话虽如此，试试这样的东西：

struct Node{
    int data;
    Node *next;
    Node *arb;

    Node(int value){
        data = value;
        next = NULL;
        arb = NULL;
    }
};

Node* resolveNode(Node *head, Node *clone, Node *target)
{
    while (head && clone){
        if (head == target)
            return clone;
        head = head->next;
        clone = clone->next;
    }
    return NULL;
}

Node* copyList(Node *head)
{
    Node *clonehead = NULL; 
    Node *ptr, **newnode = &clonehead;

    ptr = head;
    while (ptr != NULL){
        *newnode = new Node(ptr->data);
        newnode = &((*newnode)->next);
        ptr = ptr->next;
    }

    Node *cloneptr = clonehead;
    ptr = head;
    while (ptr != NULL){
        cloneptr->arb = resolveNode(head, clonehead, ptr->arb);
        cloneptr = cloneptr->next;
        ptr = ptr->next;
    }

    return clonehead;
}

或者，如果您可以节省一些额外的内存，则可以通过使用 std::(unordered_)map 来跟踪原始列表中的哪些节点对应于原始列表中的哪些节点，从而避免在第二个循环中重复列表迭代克隆列表，例如：

#include <map>

struct Node{
    int data;
    Node *next;
    Node *arb;

    Node(int value){
        data = value;
        next = NULL;
        arb = NULL;
    }
};

Node* copyList(Node *head)
{
    Node *clonehead = NULL; 
    Node *ptr, **newnode = &clonehead;
    std::map<Node*, Node*> node_lookup;

    ptr = head;
    while (ptr != NULL){
        *newnode = new Node(ptr->data);
        node_lookup.insert(std::make_pair(ptr, *newnode);
        newnode = &((*newnode)->next);
        ptr = ptr->next;
    }

    Node *cloneptr = clonehead;
    ptr = head;
    while (ptr != NULL){
        cloneptr->arb = node_lookup[ptr->arb];
        cloneptr = cloneptr->next;
        ptr = ptr->next;
    }

    return clonehead;
}

我在克隆链表时遇到问题，我的代码有什么问题？

I am having trouble cloning a linked list, what is the problem in my code?

c++

algorithm

data-structures

singly-linked-list