我在克隆鏈表時遇到問題，我的代碼有什么問題？

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

我的代碼有什么問題？

鏈接到問題：用next和隨機指標克隆一個鏈表

uj5u.com熱心網友回復：

您的代碼中有幾個錯誤：

• 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節點而不是被參考節點本身。您沒有考慮可能為 NULL 的可能性，或者克隆的 s 開始指向錯誤串列中的節點arb的事實。arb

由于每個節點arb都指向同一串列中的隨機節點，因此您不能arb在克隆節點的同一回圈中克隆 s，因為任何給定的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或者，如果您可以節省一些額外的記憶體，則可以通過使用 a來跟蹤原始串列中的哪些節點對應于克隆串列中的哪些節點，從而避免在第二個回圈中重復串列迭代，例如：

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

標籤：C 算法 数据结构 单链表

上一篇：最大堆未正確創建

下一篇：```lo==0,hi==len(cards)-1```和```lo,hi=0,len(cards)-1```有什么區別