Clone a Linked list with the Random Pointer

Posted in

Clone a Linked list with the Random Pointer

Vinay Khatri
Last updated on November 8, 2022

    Given a linked list, in which every node contains the next pointer. They also contain an additional random pointer that points to any random node present in the linked list or a null pointer in the linked list. We have to make a clone of the given Linked list that contains exactly the same number of nodes as well as the same number of pointers pointing to their respective nodes’ position in the original linked list.

    Input:

    Original Linked List:

    Output:

    ClonedLinkedList:
        7 -> 0
       13 -> 7
       11 -> 1
       10 -> 11
        1  -> 7

    Explanation:

    • The Head node in the linked list is connected to the next and null reference i.e., (7, null).
    • The second node in the linked list is connected to the next node and the head node of the linked list (13,7).
    • The third node in the linked list is connected to the next node and the last node of the linked list.
    • The fourth node is connected to the next node of the linked list and the third node of the linked list.
    • The last node is connected to the null node and the first node of the linked list.

    Approach 1

    • The Algorithm of this approach is Hashing, where we store every node of the linked list as a key and its copy as a value in the HashMap.
    • We traverse the given linked list, i.e., Original Linked List, and using a hashmap, we point the next as well as random pointer/reference of the particular node to its required position.
    • Then we return the head of the Linked list from the HashMap.

    Java Program

    //Importing all the required libraries
    import java.util.*;
    import java.util.Map.Entry;
    import java.io.*;
    class Main{
    //Creating static head Reference    
    static Node head;
    //Creating class of the Node
      static class Node{
          Node next; //next Reference to the node in the linked list
          Node random; //random Reference to the node in the linked list
          int data;  //data to be stored to the node in the linked list
          //Creating Constructor 
          public Node(int data){
              this.data=data; //Storing the data to the node
              this.next=null;
              this.next=null;
          }
      }
     //Function to Transverse the Linked list 
      static void Transverse(Node head){
     //Checking if the Linked list is null or not     
          if(head==null) {
              return ;
          }
    //Creating new reference for the head of the Linked list      
        Node temp_LinkedList=head;
     //Transverse the Linked List   
        while(temp_LinkedList!=null){
            //Checking if the random pointer is null or not
            if(temp_LinkedList.random!=null){
            System.out.println(temp_LinkedList.data+"->"+temp_LinkedList.random.data);
            }
            else{
                System.out.println(temp_LinkedList.data+"->"+0);
            }
            
            temp_LinkedList=temp_LinkedList.next;
        }
    }
    static Node clone(Node head){
        HashMap<Node,Node>H=new HashMap<Node,Node>();
        //Creating Temporary Linked list
        Node temp_LinkedList=head;
        while(temp_LinkedList!=null){
            H.put(temp_LinkedList, new Node(temp_LinkedList.data));
            temp_LinkedList=temp_LinkedList.next;
            
        }
        //Iterate the Map containing node and its reference
        for(Entry<Node,Node>node:H.entrySet()) {
            node.getValue().next=H.get(node.getKey().next);
            node.getValue().random=H.get(node.getKey().random);
        }
        //Returning the cloned linked list
        return H.get(head);
    }
     
        public static void main(String args[]){
       //Creating Head of the linked list
         head=new Node(10);
        //Creating Second node of the linked list
         head.next=new Node(11);
        //Creating third node of the linked list 
         head.next.next=new Node(12);
         //Creating fourth node of the linked list
         head.next.next.next=new Node(13);
         //Creating Random reference of the head node to the second node of the linked list. 
    head.random=head.next;
       //Creating Random reference of third node to the second node of the linked list
         head.next.next.random=head.next;
         //Printing the original linked list
         System.out.println("Original LinkedList");
         Transverse(head);
         //Creating a new line    
        System.out.println();
        
        //Cloning the linked  list
        Node clone=clone(head);
        
        System.out.println("Cloned Linkedlist");
        //Transversing the Cloned linked list
        Transverse(clone);
        }
    }

    Output

    Python Program

    #Creating node class for the linked list
    class Node:
        #Creating Constructor 
        def __init__(self, data):
            #Data to be stored in the node
            self.data = data
            #Next pointer of the node  of the Linked list
            self.next = None
            #Random pointer of the node of the Linked list
            self.random = None
    
    #Function for Traversing the Linked list
    def transverse(head):
        #Checking the base case
        if(head==None):
            return None
        #Transversing the Linked List
        while(head != None):
            #Checking the Random Reference in the node of the linked list 
            if(head.random != None):
                #If Random Reference Present in the node print 
                print(head.data,"->",head.random.data)
                
            #Condition if node does not contains random pointer    
            else:
                print(head.data,"-> 0")
              
            #Reference the next node in the linked list 
            head = head.next
    #Function to make clone of the original linked list
    def clone(head):
        #Creating temporary reference of the linked list
        origCurr = head
        #Creating map for storting the node and its copy
        mymap = {}
        #Iterate the  original linked list reference
        while(origCurr != None):
            #Storing the node and its copy in  the hash Map
            cloneCurr = Node(origCurr.data)
            mymap[origCurr] = cloneCurr
            origCurr = origCurr.next
    
        origCurr = head
        #Iterate the  original linked list reference
        while(origCurr != None):
    
            cloneCurr = mymap.get(origCurr)
            #Pointing the node to its next node
            #Pointing the node to its random node
            cloneCurr.next = mymap.get(origCurr.next)
            cloneCurr.random = mymap.get(origCurr.random)
         
            origCurr = origCurr.next
        #Returning the head 
        return mymap.get(head)
    
    #Creating First node of the linked list
    head = Node(10)
    #Creating Second node of the linked list
    head.next  = Node(11)
    #Creating Third node of the linked list
    head.next.next = Node(12)
    #Creating random reference of the First node to its own
    head.random = head
    #Printing the original Linked list
    print("Original Linked list:")
    #Transversing the original linked list
    transverse(head)
    #Printing the clone linked list
    print("Clone Linked List")
    #Calling function to create a clone of the linked list
    clone=clone(head)
    
    #Transversing the Cloned Linked list
    transverse(clone)

    Output

    C++ Program

    //Importing all the required libraries
    #include
    #include
    #include<bits/stdc++.h>
    using namespace std;
    //Creating structure for the node of linked list
    struct Node{
    int data;//data to be stored to the node in the linked list
    Node*random; //random Pointer to the node in the linked list
    Node*next;//next reference to the node in the linked list
    //Creating Constructor
    Node(int data){
    this->data=data; //Storing the data to the node
    this->next=nullptr;
    this->random=nullptr;
    }
    };
     //Function to Transverse the Linked list
    void transverse(Node *head){
         //Checking if the Linked list is null or not
        if(head==NULL){
            return;
        }
      //Transverse the Linked List
    while(head!=NULL){
            //Checking if the random pointer is null or not
    if(head->random!=NULL){
       cout<data;
       cout<<"->";
       cout<random->data;
    
    }
    else{
        cout<data;
        cout<<"-> 0 ";
    }
    cout<<"\n"; head=head->next;
    }
    
    }
     void clone(Node *head){
         if(head==NULL){
            return;
         }
    //Creating Temporary Linked list
         Node *origLinkedList = head;
         Node *cloneLinkedList = NULL;
         unordered_map<Node*, Node*> mymap_LinkedList;
    
            // Traverse the original list and make a copy in the map.
            while (origLinkedList!= NULL)
            {
                cloneLinkedList = new Node(origLinkedList->data);
               mymap_LinkedList[origLinkedList] = cloneLinkedList;
                origLinkedList = origLinkedList->next;
            }
    
            // Initialize original list again.
        origLinkedList = head;
    
              //Iterate the Map containing node and its reference
            while ( origLinkedList!= NULL)
            {
                cloneLinkedList = mymap_LinkedList[ origLinkedList];
                cloneLinkedList->next = mymap_LinkedList[ origLinkedList->next];
                cloneLinkedList->random = mymap_LinkedList[ origLinkedList->random];
                 origLinkedList =  origLinkedList->next;
            }
    
           //Transverse the head of the map
       transverse(mymap_LinkedList[head]);
    
    }
    int main(){
    //Creating Head of the linked list
    Node *head =new Node(10);
    //Creating Second node of the linked list
    head->next=new Node(11);
        //Creating third node of the linked list
    head->next->next=new Node(12);
    //Creating Random reference of the head node to its own node of the linked list.
    head->random=head;
    printf("Printing original Linked List\n");
    transverse(head);
    printf("Printing the cloned linked list\n");
    clone(head);
    return 0;
    }

    Output

    Complexity

    • Time Complexity: The Time complexity of this approach is O(n).
    • Space Complexity : The Space Complexity of this approach is O(n) because we are using the map data structure in this approach.

    Approach 2

    This approach is a little tricky, but this approach is the optimized approach to this problem. We can solve this problem in O(n) Time complexity and O(1) Space Complexity.

    • Create a copy of every node present in the original linked list and insert it to the adjacent of its parent node.
    • In the next step, Copy the random reference/Pointer from the original node and initialize it to the copied node which is adjacent to its parent node.
    • Remove all the copied nodes from the original linked list and store them in the clone linked list.
    • The clone linked list is the resultant linked list that we want.

    Input Linked List (Original Linked List):

    First Step:

    • Create a copy of every node present in the original linked list and insert it to the adjacent of its parent node.

    Second step:

    • In this step, Copy the random reference/Pointer from the original node and initialize it to the copied node which is adjacent to its parent node.

    Third step:

    • Remove all the copied nodes from the original linked list and store them in the clone linked list and make a clone linked list from the copied nodes.

    Below is the implementation of the above approach:

    Java

    import java.util.*;
    import java.util.Map.Entry;
    import java.io.*;
    class Main{
    //Creating static head Reference  
    static Node head;
    //Creating class of the Node
      static class Node{
          Node next; //next Reference to the node in the linked list
          Node random; //random Reference to the node in the linked list
          int data;  //data to be stored to the node in the linked list
          //Creating Constructor 
          public Node(int data){
              this.data=data; //Storing the data to the node
              this.next=null;
              this.next=null;
          }
      }
     //Function to Transverse the Linked list 
      static void Transverse(Node head){
     //Checking if the Linked list is null or not   
        if(head==null) {
          return ;
        }
    //Creating new reference for the head of the Linked list    
        Node temp_LinkedList=head;
     //Transverse the Linked List   
        while(temp_LinkedList!=null){
          //Checking if the random pointer is null or not
            if(temp_LinkedList.random!=null){
            System.out.println(temp_LinkedList.data+"->"+temp_LinkedList.random.data);
            }
            else{
                System.out.println(temp_LinkedList.data+"->"+0);
            }
            
            temp_LinkedList=temp_LinkedList.next;
        }
    }
      static Node clone(Node head) {
        //Creating a new reference of the head
        Node original_node=head;
        //Creating temporary reference
        Node temporary_reference=null;
        while(original_node!=null) {
          //Inserting copy of node and insert to its adjacent position in  the linked list
          temporary_reference=original_node.next;
          original_node.next=new Node(original_node.data);
          original_node.next.next=temporary_reference;
          //Update the linkedList
          original_node=temporary_reference;
          
        }
        //Initialize the head of the Linked list to the original_node
        original_node=head;
        
      while(original_node!=null) {
        //Adjust the random pointer to the new created copy node in the original linked list
        original_node.next.random=(original_node.random!=null)?original_node.random.next:null;
        //Update the position of the original Linked list
          original_node=original_node.next.next;    
      }
     
      original_node=head;
        //Creating cloning of the linked list
      Node clone=head.next;
      int count=0;
      Node temporary_reference1=clone;
    
      while(clone!=null) {
        //Copy the all the nodes from the original linked list
        clone.next=clone.next!=null?clone.next.next:clone.next;
        clone=clone.next;
      }
      //Return the cloned linked list
      return  temporary_reference1;
      }
    
     
        public static void main(String args[]){
       //Creating Head of the linked list
         head=new Node(10);
        //Creating Second node of the linked list
         head.next=new Node(11);
        //Creating third node of the linked list 
         head.next.next=new Node(12);
         //Creating fourth node of the linked list
         head.next.next.next=new Node(13);
         //Creating Random reference of the head node to the second node of the linked list. 
    head.random=head.next;
       //Creating Random reference of third node to the second node of the linked list
         head.next.next.random=head.next;
         //Printing the original linked list
         System.out.println("Original LinkedList");
         Transverse(head);
         //Creating a new line    
        System.out.println();
        
        //Cloning the linked  list
        Node clone=clone(head);
        
        System.out.println("Cloned Linkedlist");
        //Transversing the Cloned linked list
         Transverse(clone);
        }
    }

    Output

    Python Program

    #Creating node class for the linked list
    class Node:
        #Creating Constructor 
        def __init__(self, data):
            #Data to be stored in the node
            self.data = data
            #Next pointer of the node  of the Linked list
            self.next = None
            #Random pointer of the node of the Linked list
            self.random = None
    
    #Function for Traversing the Linked list
    def transverse(head):
        #Checking the base case
        if(head==None):
            return None
        #Traversing the Linked List
        while(head != None):
            #Checking the Random Reference in the node of the linked list 
            if(head.random != None):
                #If Random Reference Present in the node print 
                print(head.data,"->",head.random.data)
                
            #Condition if node does not contains random pointer    
            else:
                print(head.data,"-> 0")
              
            #Reference the next node in the linked list 
            head = head.next
    #Function to make clone of the original linked list
    def clone(head):
        #Creating temporary reference of the linked list
        original_node = head
        #//Creating temporary reference
        temporary_reference=None
        #Iterate the  original linked list reference
        while(original_node != None):
            #Inserting copy of node and insert to its adjacent position in  the linked list
            temporary_reference=original_node.next
            original_node.next=Node(original_node.data)
            original_node.next.next=temporary_reference
            #Update the node
            original_node=temporary_reference
        original_node=head
        while(original_node!=None): 
            #Adjust the random pointer to the new created copy node in the original linked list 
            original_node.next.random=original_node.random.next if original_node.random!=None else None
            #Update the position of the original Linked list
            original_node=original_node.next.next
        original_node=head
        #Creating cloning of the linked list
        clone=head.next
        temporary_reference1=clone
    
        while(clone!=None):
            #Copy the all the nodes from the original linked list
            clone.next=clone.next.next if clone.next!=None else clone.next
            clone=clone.next
        #Return the cloned linked list
        return  temporary_reference1    
    
    #Creating First node of the linked list
    head = Node(10)
    #Creating Second node of the linked list
    head.next  = Node(11)
    #Creating Third node of the linked list
    head.next.next = Node(12)
    #Creating random reference of the First node to its own
    head.random = head
    #Printing the original Linked list
    print("Original Linked list:")
    #Transversing the original linked list
    transverse(head)
    #Printing the clone linked list
    print("Clone Linked List")
    #Calling function to create a clone of the linked list
    clone=clone(head)
    
    #Transversing the Cloned Linked list
    transverse(clone)

    Output

    C++ Program

    //Importing all the required libraries
    #include
    #include
    #include<bits/stdc++.h>
    using namespace std;
    //Creating structure for the node of linked list
    struct Node{
    int data;//data to be stored to the node in the linked list
    Node*random; //random Pointer to the node in the linked list
    Node*next;//next reference to the node in the linked list
    //Creating Constructor
    Node(int data){
    this->data=data; //Storing the data to the node
    this->next=nullptr;
    this->random=nullptr;
    }
    };
     //Function to Transverse the Linked list
    void transverse(Node *head){
         //Checking if the Linked list is null or not
        if(head==NULL){
            return;
        }
      //Transverse the Linked List
    while(head!=NULL){
            //Checking if the random pointer is null or not
    if(head->random!=NULL){
       cout<data;
       cout<<"->";
       cout<random->data;
    
    }
    else{
        cout<data;
        cout<<"-> 0 ";
    }
    cout<<"\n"; head=head->next;
    }
    
    }
    void clone(Node *head){
         if(head==NULL){
            return ;
         }
    //Creating a new reference of the head
        Node *original_node=head;
        //Creating temporary reference
        Node *temporary_reference=NULL;
        while(original_node!=NULL) {
          //Inserting copy of node and insert to its adjacent position in  the linked list
          temporary_reference=original_node->next;
          original_node->next=new Node(original_node->data);
          original_node->next->next=temporary_reference;
          //Update the node
          original_node=temporary_reference;
    
        }
        //Initialize the head of the Linked list to the original_node
        original_node=head;
    
      while(original_node!=NULL) {
        //Adjust the random pointer to the new created copy node in the original linked list
        original_node->next->random=(original_node->random!=NULL)?original_node->random->next:NULL;
        //Update the position of the original Linked list
          original_node=original_node->next->next;
      }
    
      original_node=head;
        //Creating cloning of the linked list
      Node *clone=head->next;
    
      Node *temporary_reference1=clone;
    
      while(clone!=NULL) {
        //Copy the all the nodes from the original linked list
        clone->next=clone->next!=NULL?clone->next->next:clone->next;
        clone=clone->next;
      }
      //Return the cloned linked list
      transverse(temporary_reference1);
    
    
    
    }
    int main(){
    //Creating Head of the linked list
    Node *head =new Node(10);
    //Creating Second node of the linked list
    head->next=new Node(11);
        //Creating third node of the linked list
    head->next->next=new Node(12);
    //Creating Random reference of the head node to its own node of the linked list.
    head->random=head;
    printf("Printing original Linked List\n");
    transverse(head);
    printf("Printing the cloned linked list\n");
    clone(head);
    
    return 0;
    
    }

    Output:

    Complexity:

    • Time complexity : O(n). The Time Complexity of this problem is O(n).
    • Auxiliary Space :O(1). The Space Complexity of this problem is O(1).

    Conclusion

    Cloning a Linked list with the Random Pointer is one of the most frequently asked problems in most companies during technical interviews. In this article, we have discussed two approaches: one is a naive approach using map data structure and the second one is a tricky approach, and this is the most efficient approach to this problem.

    We certainly hope that this article will help you understand this problem in greater detail, and you will now be able to solve it and any variation of it quite easily.

    Happy Learning!

    People are also reading:

    Tags:
    linked list

    Leave a Comment on this Post

    0 Comments