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.
1
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 code combines node copying with in-place operations to handle the node connections. The copied nodes are interwoven with original nodes, which makes setting 'random' pointers straightforward since each copied node follows its original. After setting all pointers, it separates the intertwined nodes to complete the deep copy separation.