Unknown error in cloning a linked list of random pointers

C++ code

There is C++ code for cloning a linked list
Please refer https://www.geeksforgeeks.org/a-linked-list-with-next-and-arbit-pointer/ for details

Node* getNewNode(int data)

Node *newNode = new Node();
newNode->next = NULL;
newNode->data = data;
newNode->arb = NULL;
return newNode;

Node * copyList(Node *head)

Node *cur = head, *copy=NULL, *copy_cur, *next;
while(cur)

if(!copy)

copy = getNewNode(cur->data);
copy_cur = copy;

else

copy_cur->next = getNewNode(cur->data);
copy_cur = copy_cur->next;

cur = cur->next;

copy_cur = copy;
cur = head;
while(cur)

next = cur->next;
cur->next = copy_cur;
copy_cur->arb = cur;
copy_cur = copy_cur->next;
cur = next;

copy_cur = copy;
while(copy_cur)

copy_cur->arb = copy_cur->arb->arb->next;
copy_cur = copy_cur->next;

return copy;



Could anyone please help me in understanding the error in this implementation.

while

arb

next

while

next

next

arb

next

arb

1 Answer
1

There are couple of things need to be corrected in your code.
Your first while loop is only creating a new singly link list with next pointers set but not the "arb" pointers. Rather then creating a complete new list, just embed the new nodes in the original list only. It would be easier for you to set the random pointers afterwards.

Node newlyClonedNode = createNewNode(node->data);
newlyClonedNode->next = node->next;
node->next = newlyClonedNode;


Then again traverse the list and set the random pointers of new cloned nodes.

node->next->arb = node->arb->next;


Once you have done that, break the new list from original list, thus you get your original list back plus the new cloned list with random pointers set.

Node clonedNode = node->next;
node->next = node->next->next;

clonedNode->next = clonedNode->next->next;


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.