Copy List with Random Pointer

Question

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

The Linked List is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

val: an integer representing Node.val
random_index: the index of the node (range from 0 to n-1) where random pointer points to, or null if it does not point to any node.

LeetCodeleetcode.com/problems/copy-list-with-random-pointer

Solution

/*
@param: Node
@return: Node
Algorithm: 1.用hashmap存所有原Node, value放一个新的Node,其中val相等;
2.遍历一遍原node，依次将value中的next和random节点连起来；
*/
public Node copyRandomList(Node head) {
    if ( head == null ) return head;
    
    HashMap<Node, Node> map = new HashMap<>();
    
    for ( Node temp = head; temp != null; temp = temp.next){
        map.put(temp, new Node(temp.val, temp.next, temp.random));
    }
    
    Node result = new Node(-1,null,null);
    Node node = result;
    for ( Node temp = head; temp != null; temp = temp.next){
        map.get(temp).next = map.get(map.get(temp).next);
        map.get(temp).random = map.get(map.get(temp).random);
        node.next = map.get(temp);
        node = node.next;
    }
    return result.next;
}