138. Copy List with Random Pointer

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.

Example1

  • Recursive
public Node copyRandomList(Node head) {
    return recursive(head, new HashMap<Node, Node>());
}

public Node recursive(Node head, HashMap<Node, Node> map) {
    if(head == null) return null;
    if(map.containsKey(head)) return map.get(head);
    Node newHead = new Node();
    map.put(head, newHead);
    newHead.val = head.val;
    newHead.next = recursive(head.next, map);
    newHead.random = recursive(head.random, map);
    return newHead;
}