Replication of complex linked lists

Subject analysis

• In this case, we need to copy the linked list containing the random pointer. In this case, we first copy a normal linked list and maintain a map with the source node as the key and the new node as the value. Add a random pointer to the copied list on the second iteration.

code

/** * // Definition for a Node. * function Node(val, next, random) { * this.val = val; * this.next = next; * this.random = random; *}; * /

/ * * *@param {Node} head
 * @return {Node}* /
let copyRandomList = function (head) {
  if(! head) {return null;
  }
  let temp = head;
  const root = { next: null };
  let node = root;
  const map = new Map(a);while (temp) {
    node.val = temp.val;
    map.set(temp, node);
    if (temp.next) {
      node.next = { next: null };
      node = node.next;
    }
    temp = temp.next;
  }
  node = root;
  temp = head;
  while (temp) {
    if (temp.random) {
      node.random = map.get(temp.random);
    }
    node = node.next;
    temp = temp.next;
  }
  return root;
};
Copy the code