Copy List with Random Pointer

The key idea

The hard part is the random pointer: when you copy a node you may not have created its random target yet. Either remember the original->copy mapping in a hash map, or weave each copy in right after its original so the target copy is always reachable as original.random.next.

Problem

You are given a linked list of length n, where each node holds a val and two pointers: a normal next pointer and an extra random pointer that may point to any node in the list or to null.

Build a deep copy of the list. The copy must be made of brand-new nodes, each with the same val, where both the next and the random pointers of the new nodes point only to nodes within the copied list (never to a node in the original list).

For example, if a node in the original list points its random at the node with index 7, then the corresponding new node's random must point at the new node with index 7. Return the head of the copied list. None of the new nodes' pointers may reference the original list, and none of the original list's pointers may be changed.

Constraints

0 <= n <= 1000
-10^4 <= Node.val <= 10^4
Node.random is null or points to some node in the linked list.

Examples

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]] Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Input: head = [[1,1],[2,1]] Output: [[1,1],[2,1]]

Input: head = [[3,null],[3,0],[3,null]] Output: [[3,null],[3,0],[3,null]]

Complexity

Time: O(n) Space: O(1)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →