CareerCup

In the original list insert dummy nodes between each node, and then update the rand pointers of dummy nodes using rand pointers of the original list, thereafter, pop out all dummy nodes, it's nothing but copy of the original list.

Use the table approach.
First create a copy of the LL by parsing ones, keep the random node as NULL. Also create the table of address let assume hash on original address which store the address of corresponding duplicate node.
In the second parse look for the address of random node in the LL. look for corresponding duplicate address in the table. put this address on random part of corresponding duplicate node.

Cant we just deep clone the linked list?

// A singly link list having next and random pointer . we have to replicate of this link list.


#include<stdio.h>

// structure of link list node
struct node
{
int data;
struct node *next;
struct node *random;
};

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

if(*head_ref == NULL )
{
*head_ref = new_node;
}
else
{
while(current->next!=NULL)
{
current=current->next;
}
current->next = new_node;
}
}

/* this function will assign the random pointer to the node. random_pointer_no is the node number
which is assign as random pointer for node_number node.
*/
void random(struct node *node, int node_number, int random_pointer_no)
{
int count = 1;
struct node *temp = node;
struct node *current = node;

while(current != NULL && count != node_number ) // find out the node for which we want to assign the random pointer
{
current = current->next;
count++;
}
count = 1; // again initialize the variable for below loop
if(random_pointer_no !=1)
{
while(temp != NULL && count != (random_pointer_no-1)) // assign the next node as random pointer to the current node.
{
temp = temp->next;
count++;
}
current->random = temp->next;
}
else
current->random = node;
}

// for clone of link list
void cloneLinkList(struct node *node, struct node **node_clone)
{
// copy the original link list to new link list
struct node *current = node;
while(current != NULL)
{
struct node *current_clone = *node_clone;
struct node* new_node_clone = (struct node*) malloc(sizeof(struct node));
new_node_clone->data = current->data;
new_node_clone->next = NULL;
new_node_clone->random = NULL;

if(*node_clone == NULL )
{
*node_clone = new_node_clone;
}
else
{
while(current_clone->next!=NULL)
{
current_clone=current_clone->next;
}
current_clone->next = new_node_clone;
}
current = current->next;
}
// now i am working for random pointer of new link list
current = node;
struct node *current_clone = *node_clone;
while(current != NULL)
{
int toggle = 1;
struct node *temp = current;
struct node *temp_clone = current_clone;
while(temp->next != current->random)
{
if(temp->next == NULL) // if we reach end of first link list
{
temp = node;
temp_clone = *node_clone;
if(current->random == temp) // if first node is random pointer
{
current_clone->random = temp_clone;
toggle = 0;
break;
}
}
else
{
temp = temp->next;
temp_clone = temp_clone->next;
}
}
if(toggle) // if we dont set the random pointer already
{
current_clone->random= temp_clone->next;

}
current = current->next;
current_clone = current_clone->next;

}
}



void printlist(struct node *node)
{
while(node->next != NULL)
{
printf(" %d ->",node->data);

node = node->next;
}
printf(" %d ->NULL",node->data);

}
void printAddress(struct node *node)
{
printf("\n node value node address node next add node random address \n");
while(node != NULL)
{
printf(" %3d \t %12d \t %12d \t %12d \n",node->data,node,node->next,node->random);

node = node->next;
}

}
int main()
{
int no_node;
int index;
int val;
int random_pos;
struct node *head = NULL;
struct node *head_clone = NULL;

printf("how many node you want in link list::");
scanf("%d",&no_node);
while(no_node < 1)
{
printf("Cheater you enter less than 1 node ,\nPlease again enter number of node in link list:: ");
scanf("%d",&no_node);
}
printf("Enter the integer node data ");
for(index = 0; index < no_node; index++)
{
printf("Enter the %d data ::",(index+1));
scanf("%d",&val);
push(&head,val);
}
printf("Entered link list is :: \n");
printlist(head);

printf("\nFor Random pointer ::\n Please enter the number between 1 to %d \n", no_node);
for(index = 0;index < no_node; index++)
{
printf("for node %d , Enter Random pointer node :: ",(index+1));
scanf("%d",&random_pos);
if(random_pos < 1 || random_pos > no_node)
{
printf("You entered wrong number so i am quitting from this program");
exit(0);
}
random(head,index+1,random_pos);
}

printf("For original link listnode values with next pointer and random pointer::\n");
printAddress(head);

// for clone of link list
printf("\n process for clone link list\n");
cloneLinkList(head,&head_clone);


printf("\n clone link list is :: \n");
printlist(head_clone);

printf("\n For clone link list ,node values with next pointer and random pointer::\n");
printAddress(head_clone);


getch();
}

This seems like a graph representation using adjacency list. This can be easily cloned.

Use a map to do this - map<old list node, new list node>
do
begin
if(cur node not in map)
begin
  create new node, add that node in map
end
//set new node pointer
if(cur->next not in map)
begin
  create new node, add that node in map
  map[cur->next] = new node
end
node->next = map[cur->next]

//set random pointer

if(cur->rnd not in map)
begin
  create new node, add that node in map
  map[cur->rnd] = new node
end
node->rnd = map[cur->rnd]

cur = cur->next
End

#include <stdio.h>
#include <stdlib.h>
#include <time.h>


struct SLNode {
	int i;
	struct SLNode* next;
	struct SLNode* rand;
};

struct SLNode* create_random_list()
{
	/*rand()*/
	struct SLNode* v[10];
	int i;
	for ( i = 0; i < 10; i++ ) {
		v[i] = (struct SLNode*) malloc(sizeof(struct SLNode));
		v[i]->next = v[i]->rand = NULL;
		v[i]->i=i;
	}

	for ( i = 0; i < 9; i++ ) {
		v[i]->next = v[i+1];
		v[i]->rand = v[ rand() % 10 ];
	}
	
	v[9]->rand = v[ rand() % 10 ];

	return v[0];
}

void print_rand_list(struct SLNode* node) {

	if ( node == NULL ){
		printf("EOFL\n");
		return ;
	}

	if (node->rand != NULL)
		printf("%d(%d)->",node->i, node->rand->i);

	print_rand_list(node->next);
}

int isNodeVisited(struct SLNode* node) {
	static struct SLNode* v[10] = { NULL,NULL,NULL,NULL,NULL,
								    NULL,NULL,NULL,NULL,NULL,};
	static int cursor = 0;

	int i;

	for ( i = 0; i < cursor; i++ ) {
		if ( node == v[i] )
			return 1;
	}
	v[cursor++] = node;

	return 0;
}

struct SLNode*  DFS( struct SLNode* node ) 
{
	if ( node == NULL )
		return NULL;


	if ( !isNodeVisited(node) ) {
		struct SLNode* new_node = (struct SLNode*) malloc(sizeof(struct SLNode));
		new_node->i = node->i;
		new_node->next = DFS(node->next);
		new_node->rand = DFS(node->rand);

		return new_node;
	}

	return node;
}


void print_p( struct SLNode* p) 
{
	if ( p == NULL ) {
		printf("EOFL\n");
		return;
	}

	printf ("%p->", p);

	print_p(p->next);

}
int main(int argc, char* argv[])
{
	srand(time(NULL));
	struct SLNode* rand_lst = create_random_list();
	print_rand_list(rand_lst);
	print_p(rand_lst);

	struct SLNode* new_lst = DFS(rand_lst);
	print_rand_list(new_lst);
	print_p(new_lst);
	return 0;
}