Dare2Solve
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.
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:
random
pointers.next
pointers and random
pointers of each copied node using the mappings stored in the visited
hashmap.Implementation Steps:
visited
hashmap to store mappings from original nodes to their copied nodes.visited
, and set its val
.next
pointers of each copied node using the visited
hashmap.random
pointers of each copied node using the random_index
provided in the original node's representation.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).
O(N) due to the hashmap storing N nodes, plus the space required for the output linked list.
/*
// 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<Node*, Node*> visited;
// Function to recursively copy the linked list
function<Node*(Node*)> 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);
}
};
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]
class Solution {
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
// Map to store mapping from original nodes to their copies
Map<Node, Node> visited = new HashMap<>();
// Function to recursively copy the linked list
return copy(head, visited);
}
private Node copy(Node node, Map<Node, Node> 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;
}
}
/**
* // 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);
};