Copy List with Random Pointer

You are given a linked list where each node has Next and Random pointers. Return a deep copy of the list.

Function signature

func CopyRandomList(head *Node) *Node

Inputs / outputs

• head: head of the original list (may be nil).
• Return: head of the cloned list.

Example

1 -> 2 -> 3
random: 1->3, 2->1, 3->nil
Output: a new list with the same next/random structure

Constraints

• 0 <= number of nodes <= 100_000

Core idea (near-solution)

Use a hash map from original nodes to cloned nodes. First create all clones, then wire Next and Random using the map.

Invariant: for every original node in the map, its clone is unique and reused for all references.

Algorithm (step-by-step)

1. If head is nil, return nil.
2. First pass: traverse the list and create clone[node] = new Node(node.Val).
3. Second pass: for each original node:
   • clone[node].Next = clone[node.Next].
   • clone[node].Random = clone[node.Random].
4. Return clone[head].

Correctness sketch

• Invariant: for every original node in the map, its clone is unique and reused for all references.
• Pointer rewiring preserves all nodes and changes only their order or links.
• Each step maintains list connectivity and the intended invariant.
• When the traversal ends, the list structure matches the required transformation.

Trace (hand walkthrough)

Example input:
1 -> 2 -> 3
random: 1->3, 2->1, 3->nil
Output: a new list with the same next/random structure

Walk:
- clone nodes: 1->1', 2->2', 3->3' (map originals to clones)
- wire next: 1'->2'->3'
- wire random: 1'.random=3', 2'.random=1', 3'.random=nil

Pitfalls to avoid

• Using node values as keys (values can repeat in general; use pointers).
• Forgetting to handle nil random pointers.
• Creating new nodes on every reference instead of reusing the same clone.

Complexity

• Time: O(n).
• Extra space: O(n) for the map.

Implementation notes (Go)

• Use map[*Node]*Node.
• An alternative O(1) space method is the interleaving trick, but the map solution is simpler and clear.