/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        vector<int> arr;
        Node* rec=head;
        Node* rec1=head;
        while(rec!=NULL)
        {
            int s=0;
            while(rec1)
            {
                if(rec1==rec->random)
                {
                   arr.push_back(s);
                   break;
                } 
                s++;
                rec1=rec1->next;
            }
            if(rec1==NULL)
            arr.push_back(-1);
            rec1=head;
            rec=rec->next;
        } 
        Node* newHead=new Node(-1);
        Node* res=newHead;
        Node* temp=head;
        while(temp)
        {
            Node* newNode=new Node(temp->val);
            newHead->next=newNode;
            newHead=newNode;
            temp=temp->next;
        }
        newHead->next=NULL;
        newHead=res->next;
        Node* recc=res->next;
        int l=arr.size();
        for(int i=0;i<l;i++)
        {
            if(arr[i]==-1)
            newHead->random=NULL;
            else
            {
                Node* temptemp=recc;
                for(int j=0;j<arr[i];j++)
                {
                    temptemp=temptemp->next;
                }            
                newHead->random=temptemp;
            }
            newHead=newHead->next;
        }
        return res->next;
    }
};