Force button list question

Give you a length of n The linked list of , Each node contains an additional random pointer random , The pointer can point to any node or null node in the list .

To construct this linked list   Deep copy .  The deep copy should be made exactly by n individual new Node composition , The value of each new node is set to the value of its corresponding original node . New nodes next Pointers and random The pointer in the list should also point to the new node , And make these pointers in the original linked list and the copied linked list represent the same linked list state . The pointer in the copy linked list should not point to the node in the original linked list .

for example , If there is... In the original linked list X and Y Two nodes , among X.random --> Y . Then the corresponding two nodes in the copy linked list x and y , There are also x.random --> y .

Returns the header node of the copy linked list .

With a  n  The input is represented by a list of nodes / The linked list in the output . Each node uses one  [val, random_index]  Express ：

val： A said  Node.val  The integer of .
random_index： The index of the node that the random pointer points to （ Range from  0  To  n-1）; If you don't point to any nodes , Then for   null .
Your code only Accept the header node of the original linked list head As an input parameter .

 

Example 1：

Input ：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 ：head = [[3,null],[3,0],[3,null]]
Output ：[[3,null],[3,0],[3,null]]

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/copy-list-with-random-pointer
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

/*
// 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) {
        // 1. First traverse the old linked list , Create a corresponding new node for each old node , And insert it into  Map  in 
        Map<Node,Node> map = new HashMap<>();
        for(Node cur = head; cur != null; cur = cur.next) {
            map.put(cur,new Node(cur.val));
        }
        // 2. Traverse the old linked list again , structure  next/ random  The direction of 
        for (Node oldNode = head; oldNode != null; oldNode = oldNode.next) {
            // hold  next  Want to connect back 
            Node newNode = map.get(oldNode);
            Node newNodeNext = map.get(oldNode.next);
            newNode.next = newNodeNext;
            // hold  random  Connect with each other 
            Node newNodeRandom = map.get(oldNode.random);
            newNode.random = newNodeRandom;
        }
        return map.get(head);        
    }
}