Copy with Random Pointer

How It Works

Deep-copying a list whose nodes carry a random pointer is hard because a random pointer may target a node whose clone does not exist yet. The hash map solution makes two passes — first create all clones keyed by original node, then wire next and random through the map — at O(n) extra space. The interleaving trick removes that space: pass one splices each clone directly after its original, so the list becomes A, A', B, B', ... Pass two sets each clone's random in O(1) as original.random.next, since a clone always sits immediately after its original. Pass three unweaves the two lists, restoring the original and extracting the copy.

All three passes are linear, giving O(n) time with O(1) auxiliary space.

Step-by-Step Visualization

Code

static Node copyRandomList(Node head) {
  if (head == null) return null;
  Map<Node, Node> map = new HashMap<>();

  Node curr = head;
  while (curr != null) {
    map.put(curr, new Node(curr.val));
    curr = curr.next;
  }

  curr = head;
  while (curr != null) {
    map.get(curr).next = map.get(curr.next);
    map.get(curr).random = map.get(curr.random);
    curr = curr.next;
  }

  return map.get(head);
}

Tips & Gotchas

Practice Problems

• 1Copy List with Random Pointer
• 2Clone Graph
• 3Clone Binary Tree With Random Pointer

About the Design Problems Pattern

Build more complex data structures on top of linked lists. These combine linked lists with hash maps for O(1) operations.

Common Linked List Interview Problems

• Reverse Linked List
• Merge Two Sorted Lists
• Linked List Cycle
• Remove Nth Node From End
• LRU Cache
• Reorder List

Frequently Asked Questions

Other Design Problems Techniques