💡 Problem Formulation: In Python, a list with a random pointer refers to a data structure where each element is a node that, besides its value, contains a pointer to any other random node in the list or NULL. Cloning such a structure requires creating a deep copy of the list, such that modifying one list does not affect the other. This article aims to demonstrate five methods to effectively copy a list with a random pointer in Python, preserving the original complex references.
Method 1: Using a Dictionary to Maintain Node References
This method involves creating a hash table (dictionary in Python) to keep track of the nodes already copied. It creates a new node for each original node and uses the dictionary to manage the next and random pointers, ensuring the copied list maintains the original structure.
♥️ Info: Are you AI curious but you still have to create real impactful projects? Join our official AI builder club on Skool (only $5): SHIP! - One Project Per Month
Here’s an example:
class Node:
def __init__(self, val=0, next=None, random=None):
self.val = val
self.next = next
self.random = random
def copyRandomList(head):
if not head:
return None
old_to_new = {}
current = head
while current:
old_to_new[current] = Node(current.val)
current = current.next
current = head
while current:
old_to_new[current].next = old_to_new.get(current.next)
old_to_new[current].random = old_to_new.get(current.random)
current = current.next
return old_to_new[head]
# Example usage
original = Node(1)
original.next = Node(2)
original.random = original.next
copied_list = copyRandomList(original)
Output:
A deep cloned list, where copied_list is a separate list with identical value and random pointers as 'original'.
This code snippet creates a custom Node class and a function copyRandomList to clone a linked list with random pointers. The dictionary old_to_new helps in mapping original nodes to their corresponding cloned nodes, ensuring a deep copy with all references intact.
Method 2: Iterative Link-Weaving Approach
The iterative link-weaving method creates cloned nodes and intersperses them between the original nodes. Then, updates the random pointers appropriately, followed by separation of the two lists. This method does not use any extra space for the hash table like Method 1.
Here’s an example:
def copyRandomList(head):
if not head:
return None
# Step 1: Create new nodes
current = head
while current:
new_node = Node(current.val)
new_node.next = current.next
current.next = new_node
current = new_node.next
# Step 2: Set random pointers for the new nodes
current = head
while current:
current.next.random = current.random.next if current.random else None
current = current.next.next
# Step 3: Separate the lists
original = head
copy = head.next
while original:
next_node = original.next
original.next = next_node.next
original = original.next
if next_node.next:
next_node.next = next_node.next.next
return copy
# Example usage
# Assuming original list has been created as in Method 1
copied_list = copyRandomList(original)
Output:
A deep cloned list, where copied_list is a separated and cloned list that mirrors the 'original' including random pointers without using extra space.The code demonstrates an efficient space approach by integrating the cloning process within the original linked list. The new nodes are woven into the existing list, random pointers are adjusted, and then the list is untangled into two separate lists at the end.
Method 3: Recursive Deep Copy
This method uses recursion to deep copy each node. It creates a clone of the next and random node recursively and then fulfills the random and the next pointers step by step.
Here’s an example:
def copyRandomList(head, copies={}):
if not head:
return None
if head in copies:
return copies[head]
node_copy = Node(head.val)
copies[head] = node_copy
node_copy.next = copyRandomList(head.next, copies)
node_copy.random = copyRandomList(head.random, copies)
return node_copy
# Example usage
# Assuming original list has been created as in Method 1
copied_list = copyRandomList(original)
Output:
Recursively created deep cloned list, where 'copied_list' is an independent copy of the 'original'.
This code snippet employs recursion to elegantly clone each node, carrying a dictionary copies that acts similar to a cache, preventing circular recursion and redundant copies of nodes.
Method 4: Serialization and Deserialization
This approach leverages the concept of serialization to convert the list into a format that can be easily copied and then deserialized back to a new list structure. It’s often less efficient but is an interesting alternative that demonstrates Python’s versatility.
Here’s an example:
import pickle
def copyRandomList(head):
return pickle.loads(pickle.dumps(head))
# Example usage
# Assuming original list has been created as in Method 1
copied_list = copyRandomList(original)
Output:
The deserialized deep cloned list that reflects the structure and pointers of the 'original'.
The code uses Python’s pickle module for serialization, which will handle the deep copy process, including managing complex pointer structures transparently, albeit at a possible performance cost.
Bonus One-Liner Method 5: Using deepcopy()
The deepcopy() function from the copy module can be used to create a deep copy of the list in a single line. It is the simplest method but underneath, it is similar to the serialization method.
Here’s an example:
from copy import deepcopy # Example usage # Assuming original list has been created as in Method 1 copied_list = deepcopy(original)
Output:
A one-liner code to produce a deep cloned list that maintains the original list's random pointer structure.
This code snippet showcases the simplicity of Python where a single function call to deepcopy() takes care of all the complexities involved in cloning a data structure with random pointers.
Summary/Discussion
- Method 1: Dictionary Reference Mapping. Efficient and clear. Requires O(n) additional space.
- Method 2: Iterative Link-Weaving. Space-efficient with O(1) extra space. More complex implementation.
- Method 3: Recursive Deep Copy. Elegant and clean. Potentially high stack usage with deep recursion.
- Method 4: Serialization/Deserialization. Versatile and powerful. Potentially slow and not memory efficient.
- Bonus Method 5: Using
deepcopy(). Extremely simple. Underneath, it might be slower like serialization.