🎨Now live: Try our Free AI Image Generation Feature

Intuition
To deep copy a linked list with both next
and random
pointers, we need a strategy to maintain relationships between original nodes and their corresponding copied nodes while ensuring that each connection (both next
and random
) in the copied list points to nodes within the copied list itself.
Approach
- HashMap for Mapping: Use a hashmap (
visited
) to efficiently map each original node to its copied counterpart. This allows us to quickly retrieve copied nodes and connect them appropriately. - Two-Pass Approach:
- First Pass: Create a shallow copy of each node without connecting the
random
pointers. - Second Pass: Connect thenext
pointers andrandom
pointers of each copied node using the mappings stored in thevisited
hashmap. - Implementation Steps:
- Initialize an empty
visited
hashmap to store mappings from original nodes to their copied nodes. - Traverse the original linked list: - Create a new node for each original node, store it invisited
, and set itsval
. - Traverse the original linked list again: - Connect thenext
pointers of each copied node using thevisited
hashmap. - Connect therandom
pointers of each copied node using therandom_index
provided in the original node's representation.
Complexity
Time Complexity:
O(N), where N is the number of nodes in the linked list. We perform two passes over the list, and each hashmap operation (insertion and retrieval) is average O(1).
Space Complexity:
O(N) due to the hashmap storing N nodes, plus the space required for the output linked list.
Code
C++
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};
*/
class Solution {
public:
Node* copyRandomList(Node* head) {
if (!head) return nullptr;
unordered_map visited;
// Function to recursively copy the linked list
function copy = [&](Node* node) -> Node* {
if (!node) return nullptr;
if (visited.count(node)) return visited[node];
Node* new_node = new Node(node->val);
visited[node] = new_node;
new_node->next = copy(node->next);
new_node->random = copy(node->random);
return new_node;
};
return copy(head);
}
};
Python
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
class Solution:
def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
if not head:
return None
visited = {}
# First pass: create copies of all nodes without connecting random pointers
original = head
while original:
visited[original] = Node(original.val)
original = original.next
# Second pass: connect next and random pointers for copied nodes
original = head
while original:
copied = visited[original]
copied.next = visited.get(original.next)
copied.random = visited.get(original.random)
original = original.next
return visited[head]
Java
class Solution {
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
// Map to store mapping from original nodes to their copies
Map visited = new HashMap<>();
// Function to recursively copy the linked list
return copy(head, visited);
}
private Node copy(Node node, Map visited) {
if (node == null) {
return null;
}
// If the node has already been visited, return its copy
if (visited.containsKey(node)) {
return visited.get(node);
}
// Create a new node with the same value
Node newNode = new Node(node.val);
// Store the mapping from the original node to its copy
visited.put(node, newNode);
// Recursively copy the next and random pointers
newNode.next = copy(node.next, visited);
newNode.random = copy(node.random, visited);
return newNode;
}
}
JavaScript
/**
* // Definition for a _Node.
* function _Node(val, next, random) {
* this.val = val;
* this.next = next;
* this.random = random;
* };
*/
/**
* @param {_Node} head
* @return {_Node}
*/
var copyRandomList = function (head) {
const visited = new Map();
const copy = (node) => {
if (!node) return null;
if (visited.has(node)) return visited.get(node);
const newNode = new Node(node.val);
visited.set(node, newNode);
newNode.next = copy(node.next);
newNode.random = copy(node.random);
return newNode;
};
return copy(head);
};