The title

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

Construct a deep copy of the list. The deep copy should consist of exactly n new nodes, each of which has the same value as the original node. The next and random Pointers of the new node should also point to the new node in the replicated list, so that these Pointers in the original and replicated lists represent the same list state. No pointer in the copied list should point to a node in the original list.

For example, if the original list has two nodes X and Y, where x. randam –> Y. Then the corresponding two nodes x and y in the replicated list also have x. randam –> y.

Returns the head node of the replicated list.

The linked list in the input/output is represented by a list of n nodes. Each node is represented by a [val, random_index] :

Val: an integer representing node. val. Random_index: Index of the node to which the random pointer points (range 0 to n-1); Null if it does not point to any node. Your code only accepts the head node of the original list as an argument.

Input: the head = new Node (val, next, and the random) output: [[7, null], [13, 0], [11, 4], [10, 2], [1, 0]]
 function Node(val, next, random) {
     this.val = val;
     this.next = next;
     this.random = random;
  };

Antithesis thought

This problem is to copy a linked list structure, give you a list head, because each node has its own val, next to the next node and a random pointer to the next, according to next can draw the whole list structure along the list head, find the random pointer to each node and its own next pointer. The key to the ontology is not only to copy the value on the node, which is very easy to get, like node.val, and then recursively or looping (the next time is to copy from its next node) to get all the val as an array, but also to copy the pointer to it, which is the reference type. It must explicitly point to the same stack address as the original pointer. So, we can first iterate over all nodes in the Map data format, which has mapping relationship, so that we can easily get the original data next time. The first iterate has two purposes: new a new Node class, copy val; A deep copy of the original node to the map for the next copy of the pointer address. The second traversal is to find the original node pointed to by the pointer, and the next of the replicated node points to the same node copied in the map, how to judge the same? It’s through the key of the map. When saving, we use the original node as the key, so it is unique.

Code implementation

/** * // Definition for a Node. * function Node(val, next, random) { * this.val = val; * this.next = next; * this.random = random; *}; */ /** * @param {Node} head * @return {Node} */ var copyRandomList = function(head) { if (! head) return null; // If head is empty, return const null map = new map (); // Create a Map structure. Let node = head; // Copy the random and next Pointers while(node) {map.set(node, new node (node.val)); // Copy the random and next Pointers. // Copy a node where key is target and value is source. Copy the value node = node.next; } node = head; While (node) {const n = map.get(node); // Get the node that replicates the current node. Because I'm going to copy the pointer to him. n.next = node.next ? map.get(node.next) : null; // Determine if there is a next pointer on the original node. If there is, make the next pointer on the copied node point to the original node (in this case, the copied node), and use the key n.dom = node.random? map.get(node.random) : null; // Node = node.next; } return map.get(head); // Return the copied list. Find} by key;