138. Copy linked list with random pointer

Meaning:

Give you a linked list with a length of n. each node contains an additional random pointer random, which can point to any node or empty node in the linked list.

Construct a deep copy of this linked list. The deep copy should consist of exactly n new nodes, in which the value of each new node is set to the value of its corresponding original node. The next pointer and random pointer of the new node should also point to the new node in the replication linked list, and these pointers in the original linked list and the replication linked list can represent the same linked list state. The pointer in the copy linked list should not point to the node in the original linked list.

For example, if there are two nodes X and Y in the original linked list, where x.random -- > y. Then, the corresponding two nodes X and Y in the copy linked list also have x.random -- > y.

Returns the header node of the copy linked list.

A linked list composed of n nodes is used to represent the linked list in input / output. Each node is represented by a [val, random_index]:

Val: one represents node Integer of val.
random_index: the node index pointed by the random pointer (range from 0 to n-1); null if it does not point to any node.
Your code only accepts the head node of the original linked list as the incoming parameter.

Example 1:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

Input: head = [[1,1],[2,1]]
Output:[[1,1],[2,1]]

Example 3:

Input: head = [[3,null],[3,0],[3,null]]
Output:[[3,null],[3,0],[3,null]]

Example 4:

Input: head = []
Output:[]
Explanation: the given linked list is null (null pointer), so it returns null. 

Problem solving ideas:

With a simple solution, I did two

First:

• Create a hash table to record the correspondence between the nodes of the newly created linked list and the old nodes

• Traverse the linked list, regardless of the random pointer first Make a backup of all nodes, and then use the hash table to correspond one by one

• Re traverse the linked list. At this time, all the nodes have been created. You only need to connect the random pointer

Second:

• Create a hash table to record the correspondence between the nodes of the newly created linked list and the old nodes
• Traverse the linked list, and then create the next node to connect next Then, if you have a random node, you need to create another random node connection All created nodes should be pushed into the hash table Avoid duplicate creation

code:

First kind

class Solution {
public:
    Node* copyRandomList(Node* head) {
    if(!head)
        return nullptr;
    unordered_map<Node *, Node *> hash;
	Node *p = head;
	Node *s_head = new Node(p->val);
    hash[p] = s_head;
	Node *s = s_head;

	p = p->next;
	while (p != nullptr)
	{
		Node *newNode = new Node(p->val);
		newNode->next = nullptr;
		hash[p] = newNode;
		s->next = newNode;
		s = s->next;
        p = p->next;
	}
	p = head;
	s = s_head;
	while (p != nullptr)
	{
		s->random = hash[p->random];
        s = s->next;
		p = p->next;
	}
	return s_head;   
    }
};

Operation results:

Second:

class Solution {
public:
    Node* copyRandomList(Node* head) {
	if (!head)
		return nullptr;
	unordered_map<Node *, Node *> hash;
	Node *p = head;
	Node *s_head = new Node(p->val);
	Node *s = s_head;
	hash[p] = s_head;
	p = p->next;
	while (p != nullptr)
	{
		//Insert next node
		if (hash.find(p) != hash.end())	//If the node has been created
		{
			s->next = hash[p];
		}
		else
		{
			Node *newNode = new Node(p->val);
			hash[p] = newNode;
			s->next = newNode;
		}

		//Insert random node
		if (hash.find(p->random) != hash.end())
		{
			s->next->random = hash[p->random];
		}
		else
		{
			if (p->random != nullptr)
			{
				Node *newranNode = new Node(p->random->val);
				hash[p->random] = newranNode;
				s->next->random = newranNode;
			}
			else
			{
				s->next->random = nullptr;
			}
        }
		s = s->next;
		p = p->next;
	}    
	s = s_head;
	s_head->random = hash[head->random];
	return s_head;        
    }
};
~~~#### Summary:

t;
	}    
	s = s_head;
	s_head->random = hash[head->random];
	return s_head;        
    }
};

Operation results:

Summary:

The time complexity of the two should be the same, but the relationship between separation and non separation Separate and be logically clear