Copy the linked list with random pointer in the "Li Kou brush question plan"

Each node has three attributes ：

 

The list looks like this ： 

 

Note that the node we copied here is a reference type , That is, we copy not only the address of the node , What we need to copy is the old node .

For example, such an original linked list

Our replication does not generate another linked list exactly like the above , What we copy is a new linked list with the original linked list structure  

The value corresponding to each node of the new linked list may be the same as that of the original linked list , but next and random It must be different （ But the corresponding relationship is the same ）

  In order to maintain the corresponding relationship with each node in the original linked list in the new linked list , We need to use Map To record

Like in the picture above

  Code display ：

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        Node cur = head;
        Map<Node, Node> map = new HashMap<>(); //  If you use TreeMap The elements inside must be comparable , Only use HashMap
        //  Build the key value pair relationship between the old and new nodes , Old node is Key, The new node is Value
        while (cur != null) {
            Node tmp = new Node(cur.val); //  Construct a new node tmp, Old node is cur
            map.put(cur, tmp);
            cur = cur.next;
        }
        cur = head;
        //  Build a new node according to the node correspondence of the old linked list , Note that we are deep copy —— That is, non reference types can directly copy values , But for reference types, we copy more than address values , And the node corresponding to the reference 
        while(cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head); //  What we want to return is the new node head--- And key(head)  The corresponding  value The value is map.get(head)
    }
}