Structure of Node:

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

Now, I wrote the following code, but I am getting a segmentation fault runtime error. I can't find out what is causing this error.

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

What is wrong with my code?

Link to the problem: Clone a linked list with next and random pointer

CodePudding user response：

There are several mistakes in your code:

• clonetail->arb=ptr->arb;

  The instructions you provided are very clear that the next and arb pointers in the cloned list need to point at nodes in the cloned list, not at nodes in the original list.

• ptr->next=clonetail;

  You are modifying the next pointer of the nodes in the original list, which you should not be doing at all.

• while(ptr!=NULL){
      temp=ptr->arb;
      ptr->arb=temp->next;
      ptr=ptr->next;
  }
  

  This code makes no sense at all. You are iterating through the cloned list, and for each arb (which is pointing at a node in the original list, not in the cloned list), you are updating it to point at the referred node's next node rather than at the referred node itself. You are not taking into account the possibility that arb may be NULL, or the fact that the cloned arbs are pointing at nodes in the wrong list to begin with.

Since each node's arb is pointing at a random node in the same list, you can't clone the arbs in the same loop that is cloning the nodes, as any given arb may be referring to a later node that hasn't been cloned yet.

To clone the arbs, you would have to first finish cloning the nodes from the original list, and then iterate through the cloned list updating its arbs to point at the correct nodes within the cloned list, not the original list. I believe this is what you are attempting to do, but you are not doing it correctly.

With that said, try something more like this:

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

Alternatively, if you can spare some extra memory, you can avoid the repeated list iterations in the 2nd loop by using a std::(unordered_)map, eg:

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