Clone linked List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.



class Solution {

   //using HashMap
    public Node copyRandomList(Node head) {
        Map<Node, Node> cloneMap = new HashMap();
        Node temp = head;
        //copy list element to hashmap 
        while(temp != null){
            cloneMap.put(temp, new Node(temp.val));
            temp = temp.next;
        }
        
        temp = head;
        while(temp != null){
            cloneMap.get(temp).next = cloneMap.get(temp.next);
            cloneMap.get(temp).random = cloneMap.get(temp.random);
            
            temp = temp.next;
        }
        
        return cloneMap.get(head);
    }
    

     //pointing current.next = newNode of new list
     public Node copyRandomList(Node head) {
         Node temp = head;
         Node next = null;
         
         while(temp != null){
             next = temp.next;
             
             Node newNode = new Node(temp.val);
             
             temp.next = newNode;
             newNode.next = next;
             
             temp = next;
         }
         
         temp = head;
         while(temp != null){
             if(temp.random != null){
             temp.next.random = temp.random.next;
             
             }
             temp = temp.next.next; 
         }
         
         temp = head;
         Node newNode= new Node(0);
         Node cloneListTail = newNode;
         Node copy = null;
         
         while(temp != null){
             
             next = temp.next.next;
             copy = temp.next;
             
             cloneListTail.next = copy;
             cloneListTail = copy;
             
             temp.next = next;
             temp = next;
             
            
         }
         
         return newNode.next;
        
     }

}