Introduction to the Copy List with Random Pointer Problem
The "Copy List with Random Pointer" problem is a classic algorithmic challenge frequently encountered in coding interviews and real-world scenarios involving deep cloning of complex data structures. In this problem, you are given a linked list where each node contains a val, a next pointer to the next node in the list, and a random pointer that can point to any node in the list or be null. Your task is to create a deep copy of this list — a completely new list with identical structure and connections, but with all-new node instances.
While copying a standard singly linked list is straightforward, the presence of the random pointer introduces complexity. The random pointer can reference nodes that have not yet been created, or nodes earlier in the list, creating a non-linear dependency graph that requires careful handling.
Why This Problem Matters
This problem tests several fundamental computer science concepts simultaneously: linked list manipulation, pointer management, hash maps, and in-place algorithm design. It appears frequently in interviews at major tech companies because it effectively separates candidates who understand shallow copying from those who can implement true deep copying with complex reference structures.
In real-world applications, similar patterns emerge when cloning graphs, serializing complex object graphs, or implementing undo/redo functionality in applications where objects reference each other in non-linear ways.
Understanding the Node Structure
Before diving into solutions, let's define the node structure we will be working with throughout this tutorial:
// Definition for a Node.
function Node(val, next, random) {
this.val = val;
this.next = next;
this.random = random;
}
Each node has three properties: a value, a pointer to the next node, and a random pointer. The random pointer is what makes this problem interesting — it can point to any node in the list, including itself, or it can be null.
Approach 1: Using a Hash Map (Two Pass)
The most intuitive approach uses a hash map to store the mapping between original nodes and their copies. This approach runs in two passes: the first pass creates all the nodes and stores them in the map, and the second pass sets up the next and random pointers using the map.
How It Works
- First pass: Iterate through the original list and create a copy of each node. Store each original node as a key in a hash map with its copy as the value.
- Second pass: Iterate through the original list again. For each node, use the hash map to set the
nextandrandompointers of the copied node to the corresponding copied nodes.
Implementation
/**
* @param {Node} head
* @return {Node}
*/
var copyRandomList = function(head) {
if (!head) return null;
const map = new Map();
// First pass: create copies of all nodes
let current = head;
while (current) {
map.set(current, new Node(current.val, null, null));
current = current.next;
}
// Second pass: assign next and random pointers
current = head;
while (current) {
const copy = map.get(current);
copy.next = current.next ? map.get(current.next) : null;
copy.random = current.random ? map.get(current.random) : null;
current = current.next;
}
return map.get(head);
};
Complexity Analysis
This approach has a time complexity of O(n) because we traverse the list twice, where n is the number of nodes. The space complexity is O(n) due to the hash map storing all n nodes. This is a clean, readable solution that is easy to explain and understand during interviews.
Approach 2: Interweaving Nodes (O(1) Space)
For situations where space optimization is critical, we can solve this problem using O(1) extra space (excluding the output list). The key insight is to interweave the copied nodes with the original nodes, using the list structure itself as our "map."
How It Works
- Step 1: Insert a copy of each node immediately after the original node, creating an interweaved list like: A → A' → B → B' → C → C'.
- Step 2: Set the random pointers of the copied nodes. Since each copy sits right after its original, the random pointer of a copy can be found at
original.random.next. - Step 3: Separate the interweaved list back into two separate lists: the original and the copy.
Implementation
/**
* @param {Node} head
* @return {Node}
*/
var copyRandomList = function(head) {
if (!head) return null;
// Step 1: Insert copies after each original node
let current = head;
while (current) {
const copy = new Node(current.val, current.next, null);
current.next = copy;
current = copy.next;
}
// Step 2: Set random pointers for copies
current = head;
while (current) {
if (current.random) {
current.next.random = current.random.next;
}
current = current.next.next;
}
// Step 3: Separate the two lists
current = head;
const copyHead = head.next;
while (current) {
const copy = current.next;
current.next = copy.next;
if (copy.next) {
copy.next = copy.next.next;
}
current = current.next;
}
return copyHead;
};
Complexity Analysis
This approach maintains O(n) time complexity with three passes through the list, but reduces the space complexity to O(1) since we do not use any additional data structures. The trade-off is that the code is more complex and temporarily modifies the original list, which may not be acceptable in all scenarios.
Approach 3: Recursive Solution with Memoization
A recursive approach can also solve this problem elegantly. By using memoization, we ensure that each node is only copied once, even if multiple random pointers reference it. This approach is particularly intuitive for those comfortable with recursive thinking.
Implementation
/**
* @param {Node} head
* @return {Node}
*/
var copyRandomList = function(head) {
const map = new Map();
function copyNode(node) {
if (!node) return null;
// If we've already copied this node, return the copy
if (map.has(node)) {
return map.get(node);
}
// Create a new node and store it in the map
const copy = new Node(node.val, null, null);
map.set(node, copy);
// Recursively set next and random pointers
copy.next = copyNode(node.next);
copy.random = copyNode(node.random);
return copy;
}
return copyNode(head);
};
This recursive solution has the same O(n) time and space complexity as the hash map approach. It is elegant but may cause stack overflow issues for very long lists due to the depth of recursion.
Testing Your Solution
To verify your implementation works correctly, you should test it with various scenarios. Here is a helper function to build a list from an array of values and random pointer indices, along with test cases:
// Helper to create a list from array representation
// Each element is [val, randomIndex] where randomIndex can be null
function createList(arr) {
if (arr.length === 0) return null;
const nodes = arr.map(([val]) => new Node(val, null, null));
for (let i = 0; i < nodes.length; i++) {
if (i < nodes.length - 1) {
nodes[i].next = nodes[i + 1];
}
const randomIndex = arr[i][1];
if (randomIndex !== null) {
nodes[i].random = nodes[randomIndex];
}
}
return nodes[0];
}
// Helper to convert list back to array for verification
function listToArray(head) {
const result = [];
const nodeIndex = new Map();
let current = head;
let index = 0;
while (current) {
nodeIndex.set(current, index);
current = current.next;
index++;
}
current = head;
while (current) {
const randomIndex = current.random ? nodeIndex.get(current.random) : null;
result.push([current.val, randomIndex]);
current = current.next;
}
return result;
}
// Test cases
const test1 = createList([[7, null], [13, 0], [11, 4], [10, 2], [1, 0]]);
const copied1 = copyRandomList(test1);
console.log(listToArray(copied1));
// Expected: [[7, null], [13, 0], [11, 4], [10, 2], [1, 0]]
const test2 = createList([[1, 1], [2, 1]]);
const copied2 = copyRandomList(test2);
console.log(listToArray(copied2));
// Expected: [[1, 1], [2, 1]]
const test3 = createList([[3, null], [3, 0], [3, null]]);
const copied3 = copyRandomList(test3);
console.log(listToArray(copied3));
// Expected: [[3, null], [3, 0], [3, null]]
Best Practices
- Always handle edge cases: Check for an empty list (
nullhead) at the beginning of your function. Also consider lists with a single node and nodes where the random pointer isnull. - Choose the right approach for your context: Use the hash map approach for clarity and maintainability. Use the interweaving approach only when space is a proven constraint. Avoid the recursive approach for very large lists.
- Verify deep copy independence: After copying, modifying the original list should not affect the copy and vice versa. You can add assertions to verify that no node in the copy exists in the original list.
- Avoid modifying the input: The interweaving approach temporarily modifies the original list. If the caller expects the input to remain unchanged, ensure you fully restore it or document this behavior.
- Use null checks consistently: When accessing
current.next.nextorcurrent.random.next, always verify that intermediate pointers are notnullto avoid runtime errors.
Common Pitfalls to Avoid
One frequent mistake is attempting to set the random pointer during the first pass, before all nodes have been created. This fails because the target node of a random pointer may not exist yet. Always ensure all nodes are created before establishing random connections, or use a map to defer the connection.
Another common error is creating a shallow copy where the random pointers of the copied list still point to nodes in the original list rather than nodes in the copy. This defeats the purpose of a deep copy and can lead to subtle bugs. Always verify that random pointers in the copy reference nodes within the copy itself.
Conclusion
The Copy List with Random Pointer problem is an excellent exercise in understanding deep copying, pointer manipulation, and the trade-offs between time and space complexity. The hash map approach offers a clean, interview-friendly solution with O(n) time and space, while the interweaving approach demonstrates how to achieve O(1) space by cleverly using the existing structure as temporary storage. By mastering both approaches and understanding when to apply each, you will be well-equipped to handle not only this specific problem but also related challenges involving deep cloning of complex, interconnected data structures in your JavaScript applications.