Copy List with Random Pointer
Problem
Given the head of a linked list where 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.
- 0 ≤ Number of nodes ≤ 1000
- −10⁴ ≤ Node.val ≤ 10⁴
- Node.random is null or points to a node in the linked list
Example
head = [[7,null],[13,0],[11,4],[10,2],[1,0]][[7,null],[13,0],[11,4],[10,2],[1,0]]The input list has 5 nodes. The first node has value 7 and its random pointer is null. The second node has value 13 and its random pointer points to the first node (index 0). The third node has value 11 and its random pointer points to the fifth node (index 4). The fourth node has value 10 and its random pointer points to the third node (index 2). The fifth node has value 1 and its random pointer points to the first node (index 0). The algorithm creates a new list with new nodes having the same values and the same next and random pointer relationships, but no node is shared with the original list.
Approach
Straightforward Solution
A naive approach would be to copy nodes one by one and for each node, search the original list to find the target of its random pointer's copy. This leads to O(n^2) time complexity because for each node, locating the random pointer's copy requires a linear scan.
Core Observation
Each node in the original list must be copied exactly once, and the copied nodes must replicate the original 'next' and 'random' pointer structure. The random pointers can point arbitrarily, so a simple linear copy of 'next' pointers is insufficient. The key is to maintain a mapping from original nodes to their copies to correctly assign 'next' and 'random' pointers in the copied list.
Path to Optimal
The key recognition signals are 'deep copy', 'random pointer', and 'arbitrary pointer references'. These indicate the use of a hash map to store a mapping from original nodes to their copies. This allows O(1) lookup of any node's copy, enabling the algorithm to build the copied list in O(n) time by iterating twice: once to create all copies, and once to assign 'next' and 'random' pointers using the map.
Optimal Approach
Use a hash map that maps each original node to its copied node. First, iterate through the original list to create a copy of each node and store it in the map. Then, iterate again to assign the 'next' and 'random' pointers of each copied node by looking up the corresponding nodes in the map. Finally, return the copy corresponding to the original head. This approach guarantees O(n) time and space complexity.
Time
O(n)
The algorithm performs two passes over the list of n nodes. Each pass is O(n), and hash map lookups and insertions are O(1) on average, resulting in overall O(n) time.
Space
O(n)
The hash map stores a mapping for each of the n nodes, requiring O(n) auxiliary space. This space is necessary to maintain the correspondence between original and copied nodes.
Pattern Spotlight
Hash Maps (Node Mapping for Deep Copy)
When copying complex linked structures with arbitrary pointers, maintain a hash map from original nodes to their copies to enable constant-time lookup and correct pointer assignment, transforming a potentially quadratic problem into a linear one.
Solution
| 1 | # Definition for a Node.
|
| 2 | # class Node:
|
| 3 | # def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
|
| 4 | # self.val = int(x)
|
| 5 | # self.next = next
|
| 6 | # self.random = random
|
| 7 |
|
| 8 | class Solution:
|
| 9 | def copyRandomList(self, head: 'Node') -> 'Node':
|
| 10 | if not head:
|
| 11 | return None
|
| 12 |
|
| 13 | old_to_copy = { None: None }
|
| 14 |
|
| 15 | curr = head
|
| 16 | while curr:
|
| 17 | copy = Node(curr.val)
|
| 18 | old_to_copy[curr] = copy
|
| 19 | curr = curr.next
|
| 20 |
|
| 21 | curr = head
|
| 22 | while curr:
|
| 23 | copy = old_to_copy[curr]
|
| 24 | copy.next = old_to_copy[curr.next]
|
| 25 | copy.random = old_to_copy[curr.random]
|
| 26 | curr = curr.next
|
| 27 |
|
| 28 | return old_to_copy[head] |
| 1 | class Solution { |
| 2 | public Node copyRandomList(Node head) { |
| 3 | if (head == null) { |
| 4 | return null; |
| 5 | } |
| 6 | |
| 7 | Map<Node, Node> oldToCopy = new HashMap<>(); |
| 8 | oldToCopy.put(null, null); |
| 9 | |
| 10 | Node curr = head; |
| 11 | while (curr != null) { |
| 12 | Node copy = new Node(curr.val); |
| 13 | oldToCopy.put(curr, copy); |
| 14 | curr = curr.next; |
| 15 | } |
| 16 | |
| 17 | curr = head; |
| 18 | while (curr != null) { |
| 19 | Node copy = oldToCopy.get(curr); |
| 20 | copy.next = oldToCopy.get(curr.next); |
| 21 | copy.random = oldToCopy.get(curr.random); |
| 22 | curr = curr.next; |
| 23 | } |
| 24 | |
| 25 | return oldToCopy.get(head); |
| 26 | } |
| 27 | } |
Step-by-Step Solution
Handle Empty Input Before Starting the Deep Copy
| 10 | if not head:
|
| 11 | return None
|
Objective
To exit immediately when the input head is null, since the deep copy of an empty list is also empty.
Key Insight
Handling the empty-list case up front avoids unnecessary map setup and traversal. It also keeps the two-pass copy logic focused on the non-empty case.
Interview Quick-Check
Core Logic
Return None immediately when head is null because an empty list copies to an empty list.
State & Boundaries
This guard prevents the later copy passes from running with a null starting node.
Create Copies of All Nodes and Map Originals to Copies
| 13 | old_to_copy = { None: None }
|
| 15 | curr = head
|
| 16 | while curr:
|
| 17 | copy = Node(curr.val)
|
| 18 | old_to_copy[curr] = copy
|
| 19 | curr = curr.next
|
Objective
To create a new node for each original node and store the mapping from original to copy for later pointer assignments.
Key Insight
By iterating through the original list once and creating copies of each node without setting their pointers, the algorithm decouples node creation from pointer assignment. Storing each original node as a key and its copy as the value in a hash map enables constant-time lookup for the next phase, where pointers are assigned. This separation simplifies the logic and ensures no node is copied multiple times.
Interview Quick-Check
Core Logic
Create a copy of each node and store it in a hash map keyed by the original node to enable O(1) lookup for pointer assignment.
State & Boundaries
Iterate until the end of the original list (curr is None) to ensure all nodes are copied.
Common Pitfalls & Bugs
Forgetting to include None in the map (mapping None to None) can cause errors when assigning pointers for nodes whose next or random is None.
Assign 'next' and 'random' Pointers to Copied Nodes Using the Map
| 21 | curr = head
|
| 22 | while curr:
|
| 23 | copy = old_to_copy[curr]
|
| 24 | copy.next = old_to_copy[curr.next]
|
| 25 | copy.random = old_to_copy[curr.random]
|
| 26 | curr = curr.next
|
Objective
To correctly set the 'next' and 'random' pointers of each copied node by referencing the hash map.
Key Insight
Because the hash map contains a direct mapping from each original node to its copy, the algorithm can assign the 'next' and 'random' pointers of the copied nodes by looking up the corresponding copies of the original node's 'next' and 'random' pointers. This approach avoids searching or guessing and guarantees that all pointers in the copied list mirror the original structure exactly.
Interview Quick-Check
Core Logic
Use the hash map to assign the 'next' and 'random' pointers of each copied node by looking up the copies of the original node's pointers.
State & Boundaries
Iterate through the original list until all copied nodes have their pointers assigned.
Common Pitfalls & Bugs
Assigning pointers before all nodes are copied can lead to missing references or None pointer errors.
Return the Head of the Deep-Copied List
| 28 | return old_to_copy[head] |
Objective
To return the copied node corresponding to the original list's head as the entry point to the new list.
Key Insight
Since the hash map stores the mapping from original nodes to their copies, returning the copy of the original head node provides the caller with the deep copy of the entire list. This ensures the returned list is disconnected from the original and maintains the same structure.
Interview Quick-Check
Core Logic
Return the copied node corresponding to the original head to provide the deep copy of the entire list.
Line Analysis
This solution has 4 Critical lines interviewers watch for.
old_to_copy = { None: None }Initialize a hash map with None mapped to None.
Mapping None to None simplifies pointer assignments later by ensuring that when a node's next or random pointer is None, the copied pointer is also None without special checks.
old_to_copy[curr] = copyMap the original node to its copy in the hash map.
Storing this mapping enables O(1) lookup of the copied node for any original node, which is essential for correctly assigning 'next' and 'random' pointers later.
copy.next = old_to_copy[curr.next]Assign the 'next' pointer of the copied node.
Using the map to find the copy of the original node's 'next' ensures the copied list replicates the original's 'next' structure exactly.
copy.random = old_to_copy[curr.random]Assign the 'random' pointer of the copied node.
Similarly, assigning the 'random' pointer via the map guarantees the copied list's random pointers mirror the original's arbitrary connections.
if not head:Check if the input list is empty.
This early return handles the edge case where the input is None, avoiding unnecessary processing and returning None as the deep copy of an empty list.
copy = Node(curr.val)Create a new node copying the current node's value.
Creating a new node with the same value but without pointers decouples node creation from pointer assignment, simplifying the copying process.
return old_to_copy[head]Return the copied head node as the deep copy of the list.
Returning the copy of the original head provides the entry point to the fully constructed deep copy, completing the algorithm.
return NoneReturn None for empty input.
Returning None here correctly signals that the deep copy of an empty list is also empty, preventing errors in subsequent code.
copy = old_to_copy[curr]Retrieve the copied node corresponding to the current original node.
Accessing the copied node from the map allows pointer assignments to be made on the correct node.
while curr:Loop through the original list until the end.
This loop ensures every node in the original list is visited exactly once for copying.
while curr:Loop through the original list again to assign pointers.
This loop ensures every copied node receives correct 'next' and 'random' pointers by referencing the hash map.
curr = headStart iterating from the head of the original list.
Setting the iteration pointer to the head prepares for the first pass where all nodes are copied and stored in the map.
curr = curr.nextAdvance to the next node in the original list.
Moving the pointer forward ensures the loop progresses through all nodes without infinite looping.
curr = headReset iteration pointer to the head for second pass.
Starting a second pass from the head allows the algorithm to assign pointers to the copied nodes after all copies exist.
curr = curr.nextAdvance to the next node in the original list.
Progressing the pointer ensures all nodes are processed for pointer assignment.
Test Your Understanding
Why is a hash map necessary to correctly assign the 'random' pointers in the copied list?
Because the 'random' pointers can point arbitrarily within the list, the copied node corresponding to a random target may not be created or reachable by simple traversal. The hash map provides O(1) access to the copied node for any original node, ensuring correct and efficient assignment of 'random' pointers.
Related Problems
Hash Maps pattern
Don't just read it. Drill it.
Reconstruct Copy List with Random Pointer from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Copy List with Random Pointer drill