5.3 Deep copy a linked list with random pointer

Input: RandomListNode head

Output: RandomListNode a deep copy of head

Solution:

1. Using .clone() has a limit: if there exists references, the copy could be shallow

2. Similar to 5.2, while moving on, check if the node and node.random are in the map, connect the copied node to copied node.random

class RandomListNode {
  public int value;
  public RandomListNode next;
  public RandomListNode random;
  public RandomListNode(int value) {
    this.value = value;
  }
}

public RandomListNode copy(RandomListNode head) {
  if (head == null) {
    return head;
  }
  RandomListNode dummy = new RandomListNode(0);
  RandomListNode cur = dummy;
  Map<RandomListNode, RandomListNode> map = new HashMap<>();
  while (head != null) {
    if (!map.containsKey(head)) {
      map.put(head, new RandomListNode(head.value));
    }
 
    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;
}