Topic describes

Given a list of length n, each node contains an additional pointer random, which can point to any node or null node in the list.

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.

 

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]] example 2:

Input: head = [[1,1],[2,1]] output: [[1,1],[2,1]] example 3:

Input: the head = [[3, null], [3, 0], [3, null]] output: [[3, null], [3, 0], [3, null]] example 4:

Input: head = [] Output: [] Explanation: The given list is null (null pointer), so null is returned.

Tip:

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

Source: LeetCode link: leetcode-cn.com/problems/co… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

Their thinking

  • If the head pointer to the list points to null, null is returned.
  • Define the pointer curr to the input list head
  • Define the output of the new list of empty node node new node (); And use the temp pointer to point to the new list head node;
  • Define a map object that stores the mapping between the current node and the new node.
  • First traverse: generates a new linked list with val and next attributes; Record the relationship between the current node and the random attribute
  • Second traversal: According to the mapping relationship of map() object, the random pointer points to the corresponding node or null;

Look at the picture speak

Enter the [[1, 1] [2, 1]]Copy the code

  • The first traverse generates a linked list with val and next attributes;

      { val: 1,
    next: { 
          val: 2, 
          next: null, 
          random: null 
          }, 
    random: null }
Copy the code

  • At the same time, the mapping relationship between old and new nodes in the linked list is generated.

    • We use temp1 and temp2 to represent node 1 and node 2 in the new list respectively.

    • We use curR1 and curR2 to represent the corresponding nodes 1 and 2 in the old linked list respectively.

      map=new Map();

let temp1={ val: 1,
            next: { 
                  val: 2, 
                  next: null, 
                  random: null 
                  }, 
            random: null };

let temp2={ 
            val: 2, 
            next: null, 
            random: null 
            }
let curr1= {
            val: 1,
            next: { val: 2, 
                    next: null, 
                    random: [Circular] },
            random: { val: 2, 
                      next: null, 
                      random: [Circular] }
          };
let curr2={ val: 2, 
            next: null, 
            random: [Circular] }
  
map={

  curr1:temp1,
  curr2:temp2

}
Copy the code

  • In the second traversal, the random pointer of the new node points to the node of the map mapping relationship.

    {
  val: 1,
  next: { val: 2, next: null, random: [Circular] },
  random: { val: 2, next: null, random: [Circular] }
}
Copy the code

Space-time complexity

Time complexity: O(n), where n is the length of the list. For each node, we can access its “successor node” and “random pointer node” at most once each, evenly evenly each point is visited at most twice. O(2n)==O(n)

Space complexity: O(n), where n is the length of the list. Is the space cost of the hash table.

code

/** * // 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) {
        // Special cases will be dealt with first
    if(! head){return null;
    }
    Var ->next; var ->next; And then establish a random pointer connection
    let node=new Node(),temp=node,map=new Map(),curr=head;

    // Establish the first relationship: the first time to iterate, confirm the list of val, next attributes; Record the relationship between the current node and the random attribute.
     while(curr){ temp.val=curr.val; temp.next=curr.next! = =null? new Node():null;
         map.set(curr,temp);// map Stores the mapping of the corresponding node
         curr=curr.next;
         temp=temp.next;
     }// The list node has the same val and next attributes as the head list;

     // Establish the second relationship: the second traversal confirms the relationship of the random attribute; According to the map mapping of Curr/Temp, the random pointer points to the corresponding node or null.
     temp=node; // The temp pointer is redirected to the new list header;
     while(head){ temp.random=head.random! = =null? map.get(head.random):null;
         head=head.next;
         temp=temp.next;
     }
     return node

};
Copy the code