# [Copy List with Random Pointer](https://leetcode.com/problems/copy-list-with-random-pointer/)

## Problem Statement:
Given a linked list, return the deep copy of it.

input Linked List structure.

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

## Solution Approach
The idea is to make deep copy of every pointer and cache {original:copy} pointer and assign the `random` pointer in next iteration.

## Code

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head==NULL)
            return NULL;
        Node* copy = new Node(-1);
        Node* run = copy;
        unordered_map<Node*,Node*>cache;
        Node* t = head;
        
        while(t){
            Node* a = new Node(t->val);
            run->next=a;
            run =run->next;
            
            cache[t]=a;
            t=t->next;
        }
        
        t=head,run=copy->next;
        while(t){
            run->random = cache[t->random];
            run = run->next;
            t=t->next;
        }
        return copy->next;
    }
};