Topic describes

Their thinking

  • The Map data structure is used for the assignment
  • Key holds a pointer to a node
  • The value stores the new Node
  • The first loop builds the Map data structure
  • The second loop assigns values to the next and random fields of the value
  • Remember that the next and random fields of values here cannot point to nodes of nodes, only nodes of values in the map data structure

The implementation code

var copyRandomList = function(head) {

    // Create a Map with keys to store the head pointer field and values to store the replicated nodes
    let node = head;
    const m = new Map(a);// Iterate over the existing list
    while (node) {
        m.set(node,new Node(node.val));
        node = node.next;
    }
    // The next and random fields are empty, and the values are val to which the pointer points
    // Redirect node to head
    node = head;
    // Add next and random fields to the values in the Map data structure for the second iteration
    while (node) {
        m.get(node).next = node.next ? m.get(node.next):null;
        m.get(node).random = node.random ? m.get(node.random):null;
        node = node.next;
    }
    node = head;
    return m.get(node);

};
Copy the code