Clone linked list with next and random pointer

Clone linked list with next and random pointer

---

You are given a Doubly Link List with one pointer of each node pointing to the next node just like in a singly link list. The second pointer however can point to any node in the list and not just the previous node.
 
Lets understand the problem statement graphically and it will be more clear,

Algorithm

---

There are many ways to solve this problem, 

Approach 1: Using HashMap:

We will not able to clone complete Linked list in one iteration, because while cloning first node, we will not have access to 4th node(first node random pointer which points to 4th node) as it is not yet created.

So we need 2 iteration to clone complete linked list,

1. In first iteration, we will first clone the complete Linked list without Random pointer.
2. In second iteration, we will clone Random pointers.

 In 1st iteration we will map, 

1. original first node to cloned first node,
2. original second node to cloned second node,
3. original third node to cloned third node, and so on...

 in key-value pair in HashMap.

In 2nd iteration for cloning random pointer,

1. We will pick first node from original list and first node from cloned list.
2. Read random pointer of first node from original linked list and get the corresponding Random node in cloned list from map created in Iteration 1.
3. Assign Random pointer of first node from cloned list to corresponding node we got in   step 2.

 
Approach 2: By modifying original list(no additional space): 

In this approach, in Iteration 1, we will not use any additional space and we will modify original list and insert cloned nodes in between list as shown below.

For inserting cloned node in between original list, we need to break the direct linkages between nodes and modify linkage to support cloned node in between.  

Now our task is to set random pointer in cloned nodes.
If you observe, Node 1 random pointer points to Node 18, So for cloned Node 1 we need to point its random pointer to cloned Node 18 which is located next to original Node 18.

Similarly, Node 5 random pointer points to Node 22, So we need to point random pointer of cloned Node 5 to cloned Node 22 which is present next to source Node 22.

So in Iteration 2, we will use above technique and start setting Random pointers in cloned node.
Also, we will separate Source linked list and cloned linked list and our task is done.

Clone linked list with next and random pointer Java Program

---

package javabypatel;

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

public class CloneLinkedListWithNextAndRandomPointer {
 Node2 startNode;

 public static void main(String[] args) {
  new CloneLinkedListWithNextAndRandomPointer();
 }

 public CloneLinkedListWithNextAndRandomPointer() {
  Node2 node1 = new Node2(1);
  Node2 node2 = new Node2(2);
  Node2 node3 = new Node2(3);
  Node2 node4 = new Node2(4);

  node1.setNext(node2);
  node2.setNext(node3);
  node3.setNext(node4);
  
  node1.setRandom(node2);
  node2.setRandom(node1);
  node4.setRandom(node1);

  this.startNode = node1;

  printNodes(startNode);
  Node2 clonedStart1 = cloneLinkedListApproach2(startNode);
  System.out.println("\nCloned Node");
  printNodes(clonedStart1);
  
  Node2 clonedStart2 = cloneLinkedListApproach1(startNode);
  System.out.println("\nCloned Node");
  printNodes(clonedStart2);
 }
 
 //It prints pointer and corresponding random pointer
 public void printNodes(Node2 startNode){
  System.out.println();
  if(startNode==null)
   return;

  Node2 temp = startNode;
  while(temp!=null){
   System.out.println( temp.getData() + " " + ((temp.getRandom()==null)?"null":temp.getRandom().getData()));
   temp = temp.getNext();
  }
 }
}

Approach 1:

 //Map based approach(Time complexity O(n), Space complexity O(n))
 private Node2 cloneLinkedListApproach1(Node2 startNode) {
  if (startNode == null)
   return null;

  Node2 startNodeTemp = startNode;

  Node2 cloneStart = null;
  Node2 previousNode = null;

  Map<Node2, Node2> map = new HashMap<Node2, Node2>();

  while(startNodeTemp!=null){
   Node2 temp = new Node2(startNodeTemp.getData());

   if(cloneStart == null){
    cloneStart = temp;
    previousNode = temp;

   }else{
    previousNode.setNext(temp);
    previousNode = temp;    
   }

   map.put(startNodeTemp, temp);
   startNodeTemp = startNodeTemp.getNext();
  }

  Node2 cloneStartTemp = cloneStart;

  while(startNode!=null){
   Node2 randomTemp = map.get(startNode.getRandom());
   cloneStartTemp.setRandom(randomTemp);

   startNode = startNode.getNext();
   cloneStartTemp = cloneStartTemp.getNext();
  }
  return cloneStart;
 }

Approach 2:

 //Modifying original list approach(Time complexity O(n), Space complexity O(1))
 private Node2 cloneLinkedListApproach2(Node2 startNode) {
  if (startNode == null)
   return null;

  Node2 startNodeTemp = startNode;

  //Insert cloned nodes in between list
  while(startNodeTemp != null){
   Node2 nextPointer = startNodeTemp.getNext();

   //Creating new cloned node
   Node2 temp = new Node2(startNodeTemp.getData());

   //breaking original linking and making original node to point to cloned node.
   startNodeTemp.setNext(temp);

   //making cloned node to point to original node next.
   temp.setNext(nextPointer);

   startNodeTemp = startNodeTemp.getNext().getNext();
  }

  boolean flag = true;
  Node2 startNodeTemp1 = startNode;
  Node2 cloneStart = null;
  Node2 cloneStartTemp = null;

  //Cloning Random Pointer in cloned list and separating Cloned and Original list.
  while(startNodeTemp1 != null && startNodeTemp1.getNext()!=null){

   //Saving start pointer of cloned list.
   if(flag){
    cloneStart = startNodeTemp1.getNext();
    cloneStartTemp = startNodeTemp1.getNext();
    flag = false;
   }

   //Getting Cloned Node from list
   Node2 clonedNode = startNodeTemp1.getNext();

   //startNodeTemp1 represent original node.
   //Checking if original node random pointer points to null or to some node.
   if(startNodeTemp1.getRandom() == null){
    //original node random pointer points to null,
    //So assign cloned node random pointer points to null.
    clonedNode.setRandom(null);
   }else{
    //original node random pointer points to some node,
    //So point cloned node random pointer points to corresponding node in cloned list.
    //corresponding node in cloned list will be node next to original node random pointer 
    //because we attached cloned node next to original node in first iteration
    clonedNode.setRandom(startNodeTemp1.getRandom().getNext());
   }

   //Break original list and cloned list
   startNodeTemp1.setNext(clonedNode.getNext());
   cloneStartTemp.setNext(startNodeTemp1.getNext()); 

   //increment pointer for next iteration
   startNodeTemp1 = startNodeTemp1.getNext();
   cloneStartTemp = cloneStartTemp.getNext();
  }

  return cloneStart;
 }

package javabypatel;

public class Node2{
 private int data;
 private Node2 next;
 private Node2 random;

 public Node2(int data) {
  this.data = data;
 }

 public int getData() {
  return data;
 }

 public void setData(int data) {
  this.data = data;
 }

 public Node2 getNext() {
  return next;
 }

 public void setNext(Node2 next) {
  this.next = next;
 }

 public Node2 getRandom() {
  return random;
 }

 public void setRandom(Node2 random) {
  this.random = random;
 }
}

You may also like to see

---

Exception Handling Interview Question-Answer

Method Overloading - Method Hiding Interview Question-Answer

Advanced Multithreading Interview Questions-Answers In Java

Type Casting Interview Questions-Answers In Java

How Thread.join() in Java works internally

How is ambiguous overloaded method call resolved in java

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.