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 public int val;
public Node next;
public Node random;
public Node(int _val) {
val = _val;
next = null;
random = null;
}
}
public class Solution {
public Node CopyRandomList(Node head) {
if (head == null) return null;
Node current = head;
// Step 1: Clone and interleave nodes
while (current != null) {
Node copy = new Node(current.val);
copy.next = current.next;
current.next = copy;
current = copy.next;
}
// Step 2: Establish random pointers
current = head;
while (current != null) {
if (current.random != null) {
current.next.random = current.random.next;
}
current = current.next.next;
}
// Step 3: Unweave the lists
Node pseudoHead = new Node(0);
Node copyIter = pseudoHead;
current = head;
while (current != null) {
Node nextOrignal = current.next.next;
Node copy = current.next;
copyIter.next = copy;
copyIter = copy;
current.next = nextOrignal;
current = nextOrignal;
}
return pseudoHead.next;
}
}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.
C# implementation utilizes an interweaving method where we first clone and interleave nodes, establish the 'random' pointers effectively, and then we disentangle to extract the deep copy, operating inline, making it highly space efficient.