CareerCup

Firstly, duplicate each list node and insert them after their correspondent copied nodes， then a list with 2 * n nodes have been created;
Secondly， because every copied node's member "pNext" points to their copying node, so you can traverse the whole new list and set all new nodes' "pRandom" member;
Thirdly, split the new list into two list , one is the original list， the other is what we need。
code is as follows， may have some small bug for I have not tested it。

#include<iostream>
using namespace std;

struct node {
    struct node *pNext;
    struct node *pRandom;
};

struct node *my_clone(struct node *head)
{
    struct node *p, *q, *my_head, *r;

    if (head == NULL)
        return NULL;
    p = head;

    while (p != NULL) {
        r = new struct node();
        q = p->pNext;
        p->pNext = r;
        r->pNext = q;
        p = q;
    }

    p = head;
    while (p != NULL) {
        r = p->pNext;
        if (p->pRandom != NULL) {
            r->pRandom = p->pRandom->pNext;
        } else {
            r->pRandom = NULL;
        }
        p = r->pNext;
    }

    my_head = head->pNext;
    p = head;
    r = my_head;
    while (p != NULL) {
        q = r->pNext;
        p->pNext = q;
        p = q;
        if (q != NULL) {
            r->pNext = q->pNext;
            r = r->pNext;
        } else {
            r->pNext = NULL;
        }
    }

    return my_head;
}

Struct node* clone(Struct node *linked_list)
{
	Struct node *clone_list = (Struct node *)malloc(sizeof(Struct node));
	Struct node *temp = clone_list;
	Struct node *next = linked_list;
	int length = 0;
	while (next != 0){
		temp->pNext = (Struct node *)malloc(sizeof(Struct node));
		temp = temp->pNext;
		next = next->pNext;
		length++;
	}
	
	temp = clone_list;
	next = linked_list;
	Struct node * random;
	int count = 0;
	
	while (temp != 0){
		count = 0;
		random = next->pRandom;
		while (random != 0){
			random = random->pRandom;
			count++;
		}
		random = clone_list;
		for (int i=0;i<length - count;i++){
			random = random->pNext;
		}
		temp->pRandom = random;
		temp = temp->pNext;
		next = next->pNext;
	}
}

I believe this works, though it's not really efficient. Not sure there's a faster solution.

#include <stdio.h>
#include<string.h>
#include <stdlib.h>
#include<stdbool.h>
//#include "codeEval.h"
struct elem
{
	int data;
	struct elem *next;
	struct elem *random;

};
typedef struct elem node;
node *head=NULL,*copy=NULL;

node* newNode(int );
void addLast(int );
void display();
void freelist();


node* newNode(int c)
{
	node *new = (node*)malloc(sizeof(node));
	new->data =c;
	new->next=NULL;
	return new;
}
void addLast(int c)
{
	if(!head)
		head = newNode(c);
	else
	{
		node *walk=head;
		while(walk->next)
			walk = walk->next;
		walk->next = newNode(c);
	}
}
void display()
{
	node *walk=head;
	while(walk)
	{
		printf("%d ->",walk->data);
		walk = walk->next;
	}
		printf("\n");
}
void displayCopy()
{
	node *walk=copy;
	while(walk)
	{
		printf("c: %d ->",walk->data);
		walk = walk->next;
	}
		printf("\n");
}
void freelist()
{
	node *temp=head;
	while(temp)
	{
		head=temp->next;
		free(temp);
		temp=head;
	}
}

void setRandom(int from, int to)
{
	node *walk=head, *toRand=head;
	int i;
	if(to == -1)
		toRand = NULL;
	else
	{
		for(i=1;i<to;i++)
			toRand = toRand->next;
	}
	for(i=1;i<from;i++)
	{
		walk = walk->next;
	}
	if(toRand) printf("From %d to Random %d\n",walk->data,toRand->data);
	walk->random = toRand;

}
void populateList()
{
	addLast(12);
	addLast(5);
	addLast(25);
	addLast(23);
	addLast(8);
	display();
	//set Random from <index> to <index> index - 1 based
	setRandom(1,3);
	setRandom(2,4);
	setRandom(3,2);
	setRandom(5,4);
	setRandom(4,-1);
}
void insertList()
{
	node* walk=head;
	while(walk)
	{
		node *newN = newNode(walk->data);
		newN->next = walk->next;
		walk->next = newN;
		walk=walk->next->next;
		if(!copy)
			copy=newN;
	}
}
void displayRandom()
{
	node *walk=head;
	while(walk)
	{
		printf("%d ->",walk->data);
		walk = walk->random;
	}
		printf("\n");
	node *c=copy;
	while(c)
	{
		printf("c: %d ->",c->data);
		c = c->random;
	}
		printf("\n");
}
void copyRandom()
{
	node* walk=head;
	while(walk)
	{
		if(walk->random)
		walk->next->random = walk->random->next;
		else
			walk->next->random=NULL;
		walk=walk->next->next;
	}
	displayRandom();
}
void revertOriginal()
{
	node *walk=head;
	while(walk)
	{
		walk->next = walk->next->next;
		walk = walk->next;
	}
}
void cloneList()
{
	insertList();
	display();
	copyRandom();
	displayCopy();
	revertOriginal();
	display();
	displayCopy();

}
int main(int argc, char **argv) {
	populateList();
	cloneList();
	printf("End\n");
	return EXIT_SUCCESS;
}

how abt this code??

// let llhead be the starting of the linked list that need to be cloned

struct node * clone(struct node * llhead)
{
struct node * cchead;
struct node * temp;
struct node * lltemphead;
lltemphead = llhead;

if(lltemphead)
{
temp = (Struct node *)malloc(sizeof(Struct node));
temp->nPtr = lltemphead->nPtr;
temp->rPtr = lltemphead->rPtr;
cchead = temp;
lltemphead = lltemphead->nPtr;
}

while(lltemphead)
{
temp = (Struct node *)malloc(sizeof(Struct node));
temp->nPtr = lltemphead->nPtr;
temp->rPtr = lltemphead->rPtr;
//cchead = temp;
lltemphead = lltemphead->nPtr;
}

return cchead ;
}

you can solve it using two hashmaps
m1<Node*,int>
m2<int,Node*>

index = 0
cloneLL{
m1.put(Node*,index++);
m2.put(index,newNode*);
}

now assign random nodes
while{
node->random = m2.get(m1.get(randomNode*));
}