#include <iostream>
#include <unordered_map>
using namespace std;

class Node {
public:
	int val;
	Node* next;
	Node* random;
	Node(int _val, Node* _next = nullptr, Node* _random = nullptr) {
		val = _val;
		next = _next;
		random = _random;
	}
};

class Solution {
public:
	Node* copyRandomList(Node* head) {
		if (!head)
			return nullptr;

		unordered_map<Node*, Node*> node_map;
		Node* copy_head = nullptr;
		Node** copy = &copy_head;
		Node* node = head;

		do {
			*copy = new Node(node->val/*, nullptr, nullptr*/);
			node_map.insert(make_pair(node, *copy));
			copy = &((*copy)->next);
			node = node->next;
		}
		while (node);

		node = copy_head;

		do {
			if (head->random)
				node->random = node_map[head->random];
			node = node->next;
			head = head->next;
		}
		while (head);

		return copy_head;
	}
};

void printList(Node *head) {
	while (head) {
		cout << head << " val=" << head->val << " random=";
		if (head->random)
			cout << head->random->val << endl;
		else
			cout << "null";
		head = head->next;
	}
}

int main() {
	Node node1(1);
	Node node2(2);

	node1.next = &node2;
	node1.random = &node2;
	node2.random = &node2;

	printList(&node1);
	cout << endl;


	Node *copy = Solution{}.copyRandomList(&node1);
	printList(copy);
		
	return 0;
}