CareerCup

We can do this without modifying the list in a single pass using the hashmap where we save the reference of visited node.

public Node customizedClone(Node h){
		Node newHdr = null;
		HashMap<Node, Node> nodeHash = new HashMap<Node, Node>();
		Node temp = h;
		Node prev = null;
		while(temp != null){
			Node newNode = null;
			Node randomNode = null;
			
			if(!nodeHash.containsKey(temp)){
				newNode = new Node();
				newNode.data = temp.data;
				
				nodeHash.put(temp, newNode);
				
			}
			
			if( temp.random != null && !nodeHash.containsKey(temp.random)){
				randomNode = new Node();		
				randomNode.data = temp.random.data;
				nodeHash.put(temp.random, randomNode);
			}
			
			newNode = nodeHash.get(temp);
			randomNode = nodeHash.get(temp.random);
			newNode.random = randomNode;
			if(prev != null){
				prev.next = newNode;
			}
			else{
				 newHdr = newNode;
			}
			prev = newNode;
			temp = temp.next;
		}
		return newHdr;
	}

The space complexity is O(n) and time complexity is O(n)

www[dot]geeksforgeeks[dot]org/a-linked-list-with-next-and-arbit-pointer/

Here is my approach:

loop1:
temp = smallNode = head;
while(temp != null)
{
if(temp->data < smallNode.data)
{smallNode = temp;}
newNode = getNewNode();
newNode->data = temp->data;
nextNode = temp->next;
temp->next = newNode;
newNode->next = nextNode;
temp = nextNode;
}

loop2:
temp = smallNode;
while(temp->random != null)
{
temp->next->random = temp->random->next;
temp = temp->random;
}
temp->next->random = null;

loop3:
replicateHead = head->next;
temp = head;
replicate = replicateHead;
while(temp != null)
{
temp->next = replicate->next;
if(temp->next != null)
{replicate->next = temp->next->next;}
else
{replicate->next = null;}
temp = temp->next;
replicate = replicate->next;
}

Complexity: O(3N), O(1) space.

Can we not just traverse the linked list and create a new node for each node traversed and assign all the values (data, next pointer and random pointer) to the new node ... the random pointer that points to the successor has also got to be just assigned

It can be done in O(n) & O(1) even though random pointer is pointing to anywhere in the list.
I am not considering the space which you'll need for new list.

Assumption : Every element is unique.
1) Traverse through the linked list and create the new linked list with same data and next values and keep random pointer as NULL. For every element, save the address of current node to hash(data of current node).
e.g. 1->8->3->6->81->2
hash(1) = address of node 1
hash(8) = address of node 8
...

2) Again run the loop, and from the initial linked list; get the data value at address pointed by random pointer. Use this data as an input to hash() function to get the address in newly created linked list and assign that address in random pointer of newly created linked list.

The linked list is traversed twice, so time complexity is O(2N) = ~ O(N)
Space complexity : O(N)

Given List = 1->2->3->4->5->NULL
(I am only showing next pointer here, but you will get the idea)

Step 1 - Push a new node after every node

List - 1->1->2->2->3->3->4->4->5->5->->NULL
(Here first 1 is from old list, second 1 is new node we appended)

Step 2 - Do as following for each node.
node->next->random = node->random->next;

Step 3 - At the end just pop out newly added nodes.
and make old list's last node's next as NULL

Comments Welcome

node copy(node root){
HashMap old=new HashMap();
HashMap now=new HashMap();
int i=0,j=0;
oldfirst=root;
while(root!=null){
old.put(root,i);
root=root.next;
i++;}
node head=new node();
node first=head;
now.put(j,head);
while(j<i-1){
node tmp=new node();
head.next=tmp;
head=tmp;
j++;
now.put(j,head);}
head.next=null;
head=first;
root=oldfirst;
while(head!=null){
head.other=now.get(old.get(root));
head=head.next;
root=root.next;}
return first;}

List A
node1.next = node2;
node1.other = node3;

node2.next = node3;
node2.other = node4;

//loop the la as ListA
//lb is our new copy ListB

Node* curLa = la.begin();
Node* curLb = new Node();

// the first is the address be referred
// the second is the real address of node
// we will know second->other = first
// just consider first is single referred by one node;
// otherwise map<Node*, Node*> map_ref change to map< Node*, vector<Node*> >
map<Node*, Node*> map_ref;
map<Node*, Node*>::Iterator it;
while(curLa)
{
Node* p = new Node();
curLb->next = p;
it = map_ref.find(curLa);
if(it != map_ref.end());
{
it->first->other = p;
}

map_ref[curLa->other] = p;
curLa = curLa->next;
curLb = curLb->next;
}

I dont see what the problem is here ... we just have to make a copy right ?
we can traverse through the list using node->next;
So we start a new list and copy the contents just like copying an array.

Isint this a Graph? I can use DFS search algorithm and on every node traversal, I create a node and add corresponding links. Will update with code soon.

#include<stdio.h>

struct node
{
int data;
struct node * next;
struct node * other;

};


struct node * newnode(int data)
{
struct node * newnode=(struct node *)malloc(sizeof(struct node));
newnode->next=NULL;
newnode->other=NULL;
newnode->data=data;
return newnode;
}



void func(struct node * head1,struct node **head2)
{
static struct node * temp=NULL;
if (head1!=NULL)
{
func(head1->next,head2);
struct node * newn= newnode(head1->data);
newn->next=temp;
*head2=newn;
temp=newn;
}
}


void fun(struct node * head1, struct node **head2)
{
struct node *resultlist=*head2;
struct node *head1temp=head1->next;

while(head1!=NULL)
{
head1->next=(*head2);

(*head2)->other=head1;
(*head2)=(*head2)->next;

head1=head1temp;

if(head1temp)
  head1temp=head1temp->next;


}


*head2=resultlist;

while((*head2)!=NULL)
{
(*head2)->other=(*head2)->other->other->next;
(*head2)=(*head2)->next;
}


*head2=resultlist;

}

void printlist(struct node * root)
{
while(root!=NULL)
{
printf("\n data of node is :%d",root->data);
printf("\n other of this node is :%d",(root->other)->data);
if(root->next)
printf("\n next of this node is :%d",(root->next)->data);
printf("\n\n");
root=root->next;
}

}


int main()
{

struct node* head2=NULL;

struct node * head1=newnode(1);
head1->next=newnode(2);
head1->next->next=newnode(3);
head1->other=head1->next->next;
head1->next->other=head1;
head1->next->next->other=head1->next;

printf("\n\noriginal list is :\n \n");
printlist(head1);

func(head1,&head2);

fun(head1,&head2);

printf("\n\n copy list is :\n \n");
printlist(head2);

return 0;

}

Output:


original list is :


data of node is :1
other of this node is :3
next of this node is :2


data of node is :2
other of this node is :1
next of this node is :3


data of node is :3
other of this node is :2



copy list is :


data of node is :1
other of this node is :3
next of this node is :2


data of node is :2
other of this node is :1
next of this node is :3


data of node is :3
other of this node is :2




this is the full code in C . but it doesnt preserve the original list.

The key here is that if a node in the original list has an other pointer which is not NULL, you have to allocate the node pointed to by other as well and all other nodes along the chain to that node, in a cascading manner. This is non trivial but we might be able to leverage recursion to do this. I was too lazy to finish the code, but here's a basic outline. I'm sure there are edge cases I haven't handled.

void copy_list(node*& head, node*& tail, node*& newHead)
{
	if(head == NULL) return;

	node* ptr = head;
	while(ptr != tail)
	{
		if(ptr->other == NULL)
		{
			if(newHead == NULL)
			{
				newHead = create_node();
			}
			else
			{
				node* insertPtr = newHead;
				while(insertPtr->next != NULL) insertPtr = insertPtr->next;

				insertPtr->next = create_node();
			}
		}
		else
		{
			//recurse and create chain from "ptr" upto "other"
			node* innerHead = NULL;
			copy_list(ptr, ptr->other, innerHead);
			node* innerPtr = innerHead;
			while(innerPtr->next != NULL)
			{
				//append to list
			}
		}
	}
}

• get length of the list , let us say it is n
• create another list with all other nodes pointing to NULL. Node* other->NULL
• Traverse given list one node at a time and do following
• get other node value for given linkedlist node
• if null move to next node
• if non null do following
in new loop search for location of this address in a given original list
traverse the new list with same with
once the address is found, update the new linkedlist node' other value with node address that has been found while traversing list.

Do it in two loops.
In first loop, copy node and set only next pointer.
In second loop, copy other pointer..