/**

 * class RandomListNode {

 *   public int value;

 *   public RandomListNode next;

 *   public RandomListNode random;

 *   public RandomListNode(int value) {

 *     this.value = value;

 *   }

 * }

 */

public class Solution {

  public RandomListNode copy(RandomListNode head) {

    // Write your solution here.

    if (head == null) {

      return head;

    }

    Map<RandomListNode, RandomListNode> map = new HashMap<>();

    map.put(head, new RandomListNode(head.value));

    RandomListNode dummy = new RandomListNode(0);

    RandomListNode cur = dummy;

    while (head != null) {

      if (!map.containsKey(head)) {

        map.put(head, new RandomListNode(head.value));

      }

      // connect for the next of cur

      cur.next = map.get(head);

      if (head.random != null) {

        if (!map.containsKey(head.random)) {

          map.put(head.random, new RandomListNode(head.random.value));

        }

        cur.next.random = map.get(head.random);

      }

      head = head.next;

      cur = cur.next;

    }

    return dummy.next;

  }

}