Sponsored
Sponsored
This approach involves using a hash map to build a one-to-one mapping from the original list nodes to the copied list nodes. The algorithm consists of the following main steps:
next chain of the deep copy, while storing the mapping of original nodes to copied nodes in a hash map.random pointers in the copied list by referring back to the original nodes' random pointers.Time Complexity: O(n), where n is the number of nodes in the linked list, because we pass through the list twice.
Space Complexity: O(n) due to the use of a dictionary that stores mappings for each node.
1class Node:
2 def __init__(self, val=0, next=None, random=None):
3 self.val = val
4 self.next = next
5 self.random = random
6
7class Solution:
8 def copyRandomList(self, head: 'Node') -> 'Node':
9 if not head:
10 return None
11 # Create a dictionary to map old nodes to new nodes
12 old_to_new = {}
13
14 # First pass: copy nodes and store mapping in hash map
15 current = head
16 while current:
17 clone = Node(current.val)
18 old_to_new[current] = clone
19 current = current.next
20
21 # Second pass: assign next and random pointers
22 current = head
23 while current:
24 if current.next:
25 old_to_new[current].next = old_to_new[current.next]
26 if current.random:
27 old_to_new[current].random = old_to_new[current.random]
28 current = current.next
29
30 return old_to_new[head]The solution uses a two-pass algorithm:
next and random linkages.next and random pointers for the copied nodes. These are set using the previously built dictionary.This approach involves interleaving the cloned nodes with original ones in the same list. The three main steps include:
Time Complexity: O(n) as we traverse the list three times independently.
Space Complexity: O(1) as we only use a few additional pointers and no extra data structures.
1function Node(val, next, random) {
2 this.
This approach involves using a hash map to keep track of the relationship between the original nodes and their corresponding nodes in the copied list. First, traverse the original linked list to create a copy of each node, while storing the mapping from original nodes to copied nodes. In the second pass, assign the 'next' and 'random' pointers in the copied list based on this mapping.
Time Complexity: O(n), where n is the number of nodes in the linked list. We traverse the list twice.
Space Complexity: O(n) due to the auxiliary space used by the hash map.
This approach involves interleaving the copied nodes with the original nodes in the list. By placing each copied node immediately after its original node, the 'random' pointers can be easily assigned by looking at the 'random' pointers of the original nodes. Finally, the original and copied nodes are separated to complete the process.
Time Complexity: O(n), as we traverse the list a few times but each operation is linear.
Space Complexity: O(1), since no additional data structures are used apart from constant space variables.
1public:
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;
Node* current = head;
// Step 1: Duplicate nodes interleaved
while (current) {
Node* copy = new Node(current->val);
copy->next = current->next;
current->next = copy;
current = copy->next;
}
// Step 2: Assign random pointers to the copied nodes
current = head;
while (current) {
current->next->random = current->random ? current->random->next : nullptr;
current = current->next->next;
}
// Step 3: Detach the duplicated list from the original
Node* copyHead = head->next;
Node* copyCurrent = copyHead;
current = head;
while (current) {
current->next = current->next->next;
copyCurrent->next = copyCurrent->next ? copyCurrent->next->next : nullptr;
current = current->next;
copyCurrent = copyCurrent->next;
}
return copyHead;
}
};The solution works in three main phases:
next pointer is redirected to its clone, and the clone points to the following original node.next pointers to point to the original list and cloned list separately.The solution involves creating a deep copy of each node and storing the original-to-copy mappings in a hash map. After creating the copies, the 'next' and 'random' pointers for each copied node are assigned using the hash map. This ensures that the structure of the new list mirrors the original.
This C++ version uses a similar method: interleaving the original and copied nodes to simplify the reassignment of 'random' pointers. After interlinking and setting pointers, it detaches the copy list to form an independent deep copy.