Each of the nodes in the linked list has another pointer pointing to a random node in the list or null. Make a deep copy of the original list.

Solution: 用hashmap建立original-copy关系，先复制所有点,再复制random

  public RandomListNode copy(RandomListNode head) {
    if (head == null) {
      return head;
    }
    Map<RandomListNode, RandomListNode> hashmap = new HashMap<>();
    RandomListNode cur = head, prev = null;
    boolean isFirst = true;
    while (cur != null) {
      RandomListNode copy = new RandomListNode(cur.value);
      hashmap.put(cur, copy);
      if (isFirst) {
        prev = copy;
        isFirst = false;
      } else {
        prev.next = copy;
        prev = copy;
      }
      cur = cur.next;
    }
    cur = head;
    while (cur != null) {
      if (cur.random != null) {
        RandomListNode copy = hashmap.get(cur);
        RandomListNode copyRand = hashmap.get(cur.random);
        copy.random = copyRand;
      } 
      cur = cur.next;
    }
    return hashmap.get(head);
  }

或者可以one pass: