克隆链接列表，我遇到了困难，我的代码中有什么问题？

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;
    }

我的代码怎么了？

链接到问题：

Answer 1

您的代码中有几个错误：

• clonetail-＆gt; arb = ptr-＆gt; arb;

  您提供的指令非常清楚， 和 arb 克隆列表中的指示器需要指向克隆列表中的节点，而不是原始的节点列表。

• ptr-＆gt; next = clonetail;

  您正在修改原始列表中节点的下一个指针，您根本不应该这样做。

• 此代码完全没有意义：

    while（ptr！= null）{
      temp = ptr-＆gt; arb;
      ptr-＆gt; arb = temp-＆gt; next;
      ptr = ptr-＆gt; next;
  }
   

  您正在通过克隆列表和每个 arb （指向原始列表中的一个节点，而不是克隆列表中的一个节点），而不是在克隆列表中），您将其更新为指向节点的下一个节点，而不是在引用节点本身上。您没有考虑到 arb 的可能性，或者克隆 arb s的事实指向错误列表中的节点。 P>

由于每个节点的 arb 都指向同一列表中的一个随机节点，因此您不能在克隆节点的同一循环中克隆 arb s arb 可能是指尚未克隆的后来节点。

要克隆 arb s，您必须先完成从原始列表中克隆节点，然后通过克隆的列表迭代其 arb s，以正确地指出克隆列表中的节点，而不是原始列表。我相信这是您尝试做的，但您没有正确地做。

话虽如此，请尝试更多类似的东西：

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_）映射来避免第二循环中重复的列表迭代以保持原始列表中哪些节点的曲目对应于克隆列表中的哪些节点，例如：

#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;
}