// https://leetcode.com/problems/copy-list-with-random-pointer/description/

/*
// 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) {
        if(head == NULL) return head;

        Node *head2 = NULL, *itr2 = NULL, *itr = head;

        vector<int> pos;

        while(itr) {
            Node *newNode = new Node(itr->val);

            if(head2 == NULL) {
                head2 = newNode;
                itr2 = head2;
            }

            else {
                itr2->next = newNode;
                itr2 = itr2->next;
            }

            if(itr->random == NULL) pos.push_back(-1);
            else {
                Node* tmp = head;
                int cnt = 0;

                while(tmp != itr->random) {
                    cnt += 1;
                    tmp = tmp->next;
                }

                pos.push_back(cnt);
            }

            itr = itr->next;
        }

        itr2 = head2;
        int i = 0;

        while(itr2) {
            if(pos[i] == -1) {
                itr2->random = NULL;

            }

            Node* tmp = head2;
            for(int j = 0; j <= pos[i]; j++) {
                if(j == pos[i]) {
                    itr2->random = tmp;
                }

                else tmp = tmp->next;
            }

            itr2 = itr2->next;
            i += 1;
        }

        return head2;
    }
};