138. Copy List with Random Pointer

Reference: LeetCode
Difficulty: Medium

Problem

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.

Note: You must return the copy of the given head as a reference to the cloned list.

Example:

Input:
{"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}

Explanation:
Node 1's value is 1, both of its next and random pointer points to Node 2.
Node 2's value is 2, its next pointer points to null and its random pointer points to itself.

Analysis

Iteration

Just create the new nodes in the first pass. Don’t do anything else.

Note: map.get(null) will return null.

public Node copyRandomList(Node head) {
  Map<Node, Node> map = new HashMap<>(); // <oldNode, newNode>
  // first pass (build map)
  Node p = head;
  while (p != null) {
    Node node = new Node(p.val, null, null);
    map.put(p, node); // oldNode -> newNode
    p = p.next;
  }
  // second pass (set new)
  p = head;
  while (p != null) {
    Node node = map.get(p);
    node.next = map.get(p.next);
    node.random = map.get(p.random);
    p = p.next;
  }
  return map.get(head); // map.get(null) --> null
}

Time: $O(N)$
Space: $O(N)$

Recursion

public Node copyRandomList(Node head) {
  Map<Node, Node> map = new HashMap<>(); // <oldNode, newNode>
  return copyList(head, map);
}

private Node copyList(Node head, Map<Node, Node> map) {
  if (head == null) {
    return null;
  }
  // not in the map --> create the new node
  Node node = new Node(head.val, null, null);
  map.put(head, node);
  // copy the next first
  node.next = copyList(head.next, map);
  // set the random pointer
  node.random = map.get(head.random);
  return node;
}

Time: $O(N)$
Space: $O(N)$