CareerCup

Make two passed through link list.
Pass1: Construct new link list.Store newNode corrosponding to each oldNode in a map.
Pass2. Assing random pointer to approprate node.

Code:

Node cloneNode(Node head){

Node t = head;
Node p = null;
Node nhead = null;

while(t!= null){
	Node tmp = new Node();
	tmp.data = t.data;
    	if(p!=null){
         p.next = tmp;
        }
         else{
          nhead= tmp;
         }
        mp.put(t,tmp);
        p = tmp;
        t= t.next;
} 

mp.put(null,null);

t= head;
tmp = nhead; 
while(t!= null){
  Node n = mp.get(t.random);
  tmp.random = n;
  t= t.next;
  tmp= tmp.next;

}

return nhead;

}

this post will help you
geeksforgeeks dot org archives 1155
could you share interview place????

very good solution

Isn't this just a matter of running through the linkedlist twice. Once to create a list with next pointers and second pass for the random pointers?

Make two passed through link list.
Pass1: Construct new link list.Store newNode corrosponding to each oldNode in a map.
Pass2. Assing random pointer to approprate node.

Code:

Node cloneNode(Node head){

Node t = head;
Node p = null;
Node nhead = null;

while(t!= null){
Node tmp = new Node();
tmp.data = t.data;
if(p!=null){
p.next = tmp;
}
else{
nhead= tmp;
}
mp.put(t,tmp);
p = tmp;
t= t.next;
}

mp.put(null,null);

t= head;
tmp = nhead;
while(t!= null){
Node n = mp.get(t.random);
tmp.random = n;
t= t.next;
tmp= tmp.next;

}

return nhead;

}

Ｗｈｙ　ｎｅｅｄ　ｔｏ　ｇｏ　ｔｈｒｏｕｇｈ　ｔｈｅ　ｌｉｓｔ　ｔｗｉｃｅ？　Why random pointers cannot be copied with the “next” pointer? What is the mp.get function? Can we do this without this function?

I tried the same problem and I got the required output .
Below is the code:
#include<stdio.h>
#include"malloc.h"
#include"conio.h"

struct node
{
struct node *next;
struct node *random;
int val;

};

void printList(struct node *head)
{
while(head!=NULL)
{
printf("\nval = %d\t random = %d ",head->val,head->random->val);
head=head->next;
}
printf("\n");
}

void push(struct node **head_ref, int new_data)
{
struct node *new_node =
(struct node *)malloc(sizeof(struct node));
new_node->val= new_data;
new_node->next = *head_ref;
*head_ref = new_node;

}
struct node* copy_list(struct node *root)
{
printf("\ninside copy_list: ");
struct node *res=NULL;

struct node *cur = root;
struct node *next, *tail=NULL;


while(cur != NULL)
{
printf("val = %d\t random = %d ",cur->val,cur->random->val);
if(res == NULL)
{
push(&res, cur->val);

res->random = cur->random;

tail = res;
printList(tail);
}
else
{


push(&(tail->next),cur->val);

tail=tail->next;
tail->random = cur->random;


}
cur = cur->next;
}


printf("\nres printing");
printList(res);
return res;

}



int main()
{
printf("Given Linked List: ");
struct node *head = NULL;

/* Create following linked list
1->2->3->4->5 and
random of 1 -> 3
random 0f 2->1
random of 3->5
random of 4 ->5
random of 5->2*/

push(&head,5);
push(&head,4);
push(&head,3);
push(&head,2);
push(&head,1);
head->random = head->next->next;
head->next->random = head;
head->next->next->random = head->next->next->next->next;
head->next->next->next->random = head->next->next->next->next;
head->next->next->next->next->random = head->next;

printf("\nGiven Linked List: ");
printList(head);

head=copy_list(head);

printf("\nGiven Linked List After perform: ");
printList(head);
getch();
}

can anyone pls check and suggest if this code is correct ?