HashMap approach — O(N) space

Node copy(Node head) {
  Map map = new HashMap<>();
  for (Node cur = head; cur != null; cur = cur.next)
    map.put(cur, new Node(cur.val));
  for (Node cur = head; cur != null; cur = cur.next) {
    map.get(cur).next = map.get(cur.next);
    map.get(cur).random = map.get(cur.random);
  }
  return map.get(head);
}
Advertisement

Interleave trick — O(1) space

// 1. Insert copy after each original: A -> A' -> B -> B' -> ...
// 2. Set copy.random = original.random.next
// 3. Separate lists: original.next = original.next.next, copy.next = copy.next.next
Advertisement

Why interleave works

Copy nodes physically follow originals. Original's random points to some node X. Copy's random should point to X's copy = X.next.

Complexity

Both: O(N) time. HashMap: O(N) space. Interleave: O(1) extra space (aside from output).