Type like pro

# Linked list with random pointer

## Problem

A linked list is given where every node of the linked list has one next pointer and one additional pointer called random, which points to any arbitrary node in the linked list. Write a method to deep copy this linked list

## Solution

First the linked list is normally deep copied to a new linked list. While creating every node of the destination linked list, we create a map where key is the source node and value is the corresponding destination node. This map is later used to populate the random pointer. We again traverse the source linked list. For each node we take the node pointed by its random pointer and search it in the map, as the value is the corresponding node in destination linked list, we populate the random pointer accordingly.

## Code

```import java.util.HashMap;
import java.util.Map;

{

public static void main(String[] args)
{
NodeRandom a=new NodeRandom(4);
NodeRandom b=new NodeRandom(5);
NodeRandom c=new NodeRandom(3);
NodeRandom d=new NodeRandom(6);
NodeRandom e=new NodeRandom(7);
NodeRandom f=new NodeRandom(2);
NodeRandom g=new NodeRandom(9);
NodeRandom h=new NodeRandom(3);
NodeRandom i=new NodeRandom(7);
a.next=b;
b.next=c;
c.next=d;
d.next=e;
e.next=f;
f.next=g;
g.next=h;
h.next=i;
a.random=g;
b.random=a;
c.random=e;
d.random=f;
e.random=e;
f.random=null;
g.random=b;
h.random=i;
i.random=f;

}
{
{
}
System.out.println();
}
{
Map<NodeRandom,NodeRandom> map=
new HashMap<NodeRandom, NodeRandom>();
NodeRandom destPtr=null;
while(sourcePtr!=null)
{
{
}
else
{
destPtr.next=new NodeRandom(sourcePtr.value);
destPtr=destPtr.next;
}
map.put(sourcePtr, destPtr);
sourcePtr=sourcePtr.next;
}
while(sourcePtr!=null)
{
destPtr.random=map.get(sourcePtr.random);
sourcePtr=sourcePtr.next;
destPtr=destPtr.next;
}
}

static class NodeRandom
{
public NodeRandom next;
public NodeRandom random;
public int value;
public NodeRandom(int value)
{
this.value=value;
}
public String toString()
{
if(random==null)
return "{"+hashCode()+"("+value+") r->null}";
else
return "{"+hashCode()+"("+value+") r->"+
random.hashCode()+"}";
}
}
}
```