Leetcode-138-copy linked list with random pointer

subject

Ideas

1. No idea , Copy the linked list to copy , however random The node position is not easy to record , Even if it is recorded, it must be traversed every time , If exactly all nodes point to the last node, it is O(n^2) Time complexity of .
2. Have you thought about the solution of the problem , But at that time, I wanted to hash the node values of the linked list , But the node value will repeat , So it got stuck , Originally, you can store nodes directly , Solve with recursion … Learned .

Code

    // Building hash tables   It is used to correspond to the original node and the current node 
    Map<Node,Node> cacheNode = new HashMap<Node,Node>();
    public Node copyRandomList(Node head) {
    
        // This is the end point of recursion 
        if(head==null) return null;
        if(!cacheNode.containsKey(head)){
     // If the hash table key Not included head  That is, the node has not been created 
            // With head Create a new node
            Node headNew = new Node(head.val);
            cacheNode.put(head,headNew);
            head.next = copyRandomList(head.next); // Recursion is completed by default   Already copy Out of its next node 
            head.random = copyRandomList(head.random);// The principle of same 
        }
        // If it has been included , Just return to the new node 
        return cacheNode.get(head);
    }