Copy Linked List

A new type of linked list is given. It's structure has 3 elements, data, next pointer, unknown pointer. data and next pointer are same as in normal linked list. The unknown pointer is pointing to any random node in that linked list. Now, write a code which will copy this linked list.










SOLUTION

node * copy( node * head){
node *p = head, *q=NULL, *NewHead=NULL;
while( p){
node * q = new node;
q->next = p->unknown;
p->unknown = q;
p = p->next;
}

NewHead = head->unknown;
p = head;

while(p){
q = p->unknown;
q->unknown = q->next->unknown;
p = p->next;
}

p = head;

while (p){
q = p->unknown;
p->unknown = q->next;
if (p->next)
q->next = p->next->unknown;
else
q->next = NULL;
p=p->next;
}


return NewHead;
}