“This is the 11th day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021”

Copy a linked list with a random pointer

Power button link

You are given a list of length N, and each node contains an additional random pointer, random, which can point to any node or empty node in the list.

Construct a deep copy of the list. The deep copy should consist of exactly N new nodes, with each new node set to the value of its corresponding 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 a replicated list should point to a node in the original list.

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

Returns the head node of the replication list.

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

Val: an integer representing Node.val. Random_index: the 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 accepts only the head of the original list as an argument.

Tip:

  • 0 <= n <= 1000
  • -10000 <= Node.val <= 10000
  • Node.randomIs null or points to a node in the linked list.

Example 1:

Input: the head = [[7, null], [13, 0], [11, 4], [10, 2], [1, 0]] output: [[7, null], [13, 0], [11, 4], [10, 2], [1, 0]]Copy the code

Example 2:

Input: the head = [[7, null], [13, 0], [11, 4], [10, 2], [1, 0]] output: [[7, null], [13, 0], [11, 4], [10, 2], [1, 0]]Copy the code

Hash table + traversal

Train of thought

  • Complete clone, cannot point to old node

Difficult points:

  • How do you clone a node and know which node it originally points to

Here we use Map data to do this. Any value (object or raw value) of Map type in JS can be a key or a value.

In order to know a location information corresponding to each node in the original object, we directly take the source node as the key and value as the clone node of the source node

This way each source node can uniquely correspond to a new clone node, and the problem is solved

Problem solving:

We’re going to walk through the original list, and we’re going to use getCloneVal to get a new clone of the current node

If the key value is null, null is returned. If not, the node exists in the nodeMap. If not, create a new node and return the new clone node.

At the end of the iteration, the head pair in the nodeMap is returned as the new cloned linked list

var copyRandomList = function (head) {
    var nodeMap = new Map(a);var head1 = head;
    function getCloneVal(obj) {
      if(! obj)return null;
      if(! nodeMap.get(obj)) nodeMap.set(obj,{val:obj.val})
      return nodeMap.get(obj)
    }
    while (head1) {
      var curr = getCloneVal(head1)
      curr.next = getCloneVal(head1.next);
      curr.random = getCloneVal(head1.random);
      head1 = head1.next;
    }
    return nodeMap.get(head);
  };
Copy the code

Hash table plus recursion

Train of thought

We’re going to do it recursively

  • Creating a Map Object
  • If the head node is not empty, the head node is saved in the Map as the key and its clone value is Val
  • Continue to call the copyRandomList function to recursively process the next and random Pointers to head
  • Finally, return the header of the Map object
var copyRandomList = function(head, cachedNode = new Map(a)) {
    if (head === null) {
        return null;
    }
    if(! cachedNode.has(head)) { cachedNode.set(head, {val: head.val}), Object.assign(cachedNode.get(head), {next: copyRandomList(head.next, cachedNode), random: copyRandomList(head.random, cachedNode)})
    }
    return cachedNode.get(head);
}

Copy the code

Iteration + node splitting

Train of thought

Node splitting means that we clone the node after each node in the list and place it between the next node and the next node

So A->B->C becomes A->A’->B->B’->C->C’

The idea is similar to that of a map table. A map table uses the key to find the corresponding clone node. Node splitting uses the next of the source node to find its clone node

In this way, we can copy the operation of the source node completely, and finally split the clone node separately

  • First, we need to add cloned nodes and make the linked list longer. Here, we iterate through the linked list with each step size as next. Next
  • The replication source node random is traversed for the second time
  • Next in the linked list is iterated for the third time, and next of the cloned linked list is separated separately

Finally, return a new headNew

var copyRandomList = function(head) {
    if (head === null) {
        return null;
    }
    for (letnode = head; node ! = =null; node = node.next.next) {
        const nodeNew = new Node(node.val, node.next, null);
        node.next = nodeNew;
    }
    for (letnode = head; node ! = =null; node = node.next.next) {
        constnodeNew = node.next; nodeNew.random = (node.random ! = =null)? node.random.next :null;
    }
    const headNew = head.next;
    for (letnode = head; node ! = =null; node = node.next) {
        constnodeNew = node.next; node.next = node.next.next; nodeNew.next = (nodeNew.next ! = =null)? nodeNew.next.next :null;
    }
    return headNew;
};

Copy the code