Solution is to clone the list by modifying 'next' in this way first:
Original
-->1 2-------| 3-------| 4-------|
| /|\ | /|\ | /|\ |
\|/ | \|/ | \|/ | \|/
-->1------ | 2-------| 3-------| 4
Cloned
And then, map all the random pointers in the original list to the cloned list. Their correspondence makes this easy now.
And finally, map the next pointers to their original nodes.
--------------------------------------------------------------------------------------------------------------------------
import java.util.*;
import java.lang.*;
import java.io.*;
class CloneLinkedList
{
public static void main (String[] args) throws java.lang.Exception
{
// create LL
Node head = createNewNode(1);
Node two = createNewNode(2);
Node three = createNewNode(3);
Node four = createNewNode(4);
head.next = two;
two.next = three;
three.next = four;
head.random = three;
two.random = four;
Node clonedList = clone(head);
Node current = clonedList;
while(current != null)
{
System.out.println("val: "+ current.value );
if( current.random != null)
System.out.println(" random: " + current.random.value);
current = current.next;
}
}
public static Node clone(Node head)
{
if( head == null )
{
return null;
}
Node current = head;
while( current != null)
{
Node temp = createNewNode(current.value);
temp.next = current.next;
current.next = temp;
current = temp.next;
}
Node clonedHead = head.next;
current = head;
while( current != null )
{
if( current.random != null)
{
current.next.random = current.random.next;
}
current = current.next.next;
}
current = head;
while( current != null )
{
Node temp = current.next;
current.next = temp.next;
current = current.next;
if( current != null)
{
temp.next = current.next;
}
}
return clonedHead;
}
public static Node createNewNode(int value)
{
Node node = new Node(value);
return node;
}
}
class Node
{
int value;
Node next;
Node random;
public Node(int val)
{
value = val;
}
}
--------------------------------------------------------------------------------------------------------------------------
Cases that need caution:
1. Random could be null or might point in reverse direction.
2. Edge case when mapping next pointers back. temp.next can only point to current.next when current is non null.
--------------------------------------------------------------------------------------------------------------------------
Test Execute it here
