CareerCup

We can use hashmaps to do it in O(n) time
algo::
1.copy the linked list with next pointers(arbitrary may be NULL)
All use a hash function
Say Pi denote original linked list pointers,Qi-cloned linked list pointers,h-hash fn
so,while creating cloned linked list...store h(Pi)=Qi for all pointers
2.Now,once the list is created.repeat for each Pi
h(Pi)->arbitrary=h(Pi->arbitrary)
Pi=Pi->next;

// Cloning a linked list in O(n)
#include<conio.h>

#include<stdio.h>
#include<malloc.h>

typedef struct NODE
{
int data;
struct NODE *next;
struct NODE *arbt;
}node;

typedef struct addbook
{
struct addbook *next;
node *point;
}book;
void printli(node *href)
{
node *counter = href;
while(counter)
{
printf("%d\t",counter->data);
counter = counter->next;
}
}

void addNode(node **href, int data)
{
// printf("Entereed the add node fucntion\n");
node *newNode = (node*)malloc(sizeof(node));
newNode->data = data;
newNode->next = NULL;
node *temp;// (node*)malloc(sizeof(node));
temp = (*href);
if(temp == NULL)
(*href) = newNode;
else
{
while(temp->next)
{
temp = temp->next;
}
temp->next = newNode;
}
}

void printList(node *href)
{
node *counter = (node*)malloc(sizeof(node));
counter = href;

int i=0;
while(counter)
{
printf("CURRENT NODE = %d\t ARBT NODE = %d\n",counter->data,counter->arbt->data);
counter = counter->next;
}
}


void cloneList(node **href1, node **href2)
{
book b[5];
node *currNode;
node *prevNode = (node*)malloc(sizeof(node));
node *nextNode = (node*)malloc(sizeof(node));
currNode = (*href1);
node *temp = (*href2);
int i = 0;
while(currNode)
{
// printf("currNode ->data1 = %d\n", currNode->data);
addNode(href2,currNode->data);
temp = (*href2);
b[i].point = currNode->next;
i++;
nextNode = currNode->next;
prevNode = currNode;
currNode = nextNode;
// printf("temp->val = %d\n",temp->data);
while(temp->next)
{
temp = temp->next;
}
prevNode->next = temp;
temp->arbt = prevNode;
// printf("currNode ->data2 = %d\n", currNode->data);
}
temp = (*href2);
while(temp)
{
temp->arbt = temp->arbt->arbt->next;
temp = temp->next;
}

temp =(*href1);
i=0;
while(temp)
{
temp->next = b[i].point;
temp = temp->next;
i++;
}


}




int main()
{
node *root= (node*)malloc(sizeof(node));
root = NULL;

addNode(&root,1);
addNode(&root,2);
addNode(&root,3);
addNode(&root,4);
addNode(&root,5);

//printli(root);

root->arbt = root->next;
(root->next)->arbt = root->next->next;
(root->next->next)->arbt = root->next->next->next->next;
(root->next->next->next)->arbt = root;
root->next->next->next->next->arbt = root->next;
//

printList(root);

node *list2 = (node*)malloc(sizeof(node));
list2 = NULL;
cloneList(&root,&list2);
printf("\n");
printList(list2);

// printList(list2);
return 0;

}