Replication of complex linked list

Title Description ： Please implement copyRandomList function , Copy a complex list . In complex linked list , Each node has one next The pointer points to the next node , One more random The pointer points to any node in the list or NULL;

Question ： The copy of linked list can directly traverse the linked list , Create a new node implementation , there random What does the pointer do ？

Problem solving ： As the title says , What is needed here is the replication of complex linked lists , there random It doesn't matter what the pointer does , The important thing is how to copy the random pointer correctly .

Ideas ： Using the query characteristics of hash table , Consider building the key value mapping relationship between the original linked list node and the corresponding node of the new linked list , Then traverse the nodes of the new linked list next and random Reference points to . In other words, traverse both sides , The first time, only build new nodes , Build a new node for the second time next and cur.

The illustration ：

  Code implementation ：

Node* copyRandomList(Node* head)
{
	if (head == NULL)return NULL;
	unordered_map<Node*, Node*>map;
	Node* cur = head;
	while (cur != NULL)
	{
		map[cur] = new Node(cur->val);
		cur = cur->next;
	}
	cur = head;
	while (cur != NULL)
	{
		map[cur]->next = map[cur->next];
		map[cur]->random = map[cur->random];
		cur = cur->next;
	}
	return map[head];
}