Clone Linked List with Random Pointer in DSA Python - Build from Scratch

Clone Linked List with Random Pointer

📖 Scenario: Imagine you have a special linked list where each node has two pointers: one points to the next node, and another points randomly to any node in the list or None. This structure is used in complex applications like social networks to represent friends and random connections.

🎯 Goal: You will build a program to create a deep copy (clone) of this linked list. The cloned list should have new nodes with the same values, and the next and random pointers should point to the corresponding cloned nodes, not the original ones.

📋 What You'll Learn

Create a Node class with val, next, and random attributes

Create the original linked list with 3 nodes and specific random pointers

Use a dictionary to map original nodes to their clones

Implement the cloning logic to copy next and random pointers correctly

Print the cloned list nodes showing their val and the val of their random pointers

💡 Why This Matters

🌍 Real World

Cloning complex linked structures is useful in applications like social networks, game development, and memory management where objects have multiple references.

💼 Career

Understanding how to clone data structures with complex pointers is important for software engineers working on system design, debugging, and optimizing memory usage.

1

Create the Node class and original linked list

Define a class called Node with an __init__ method that takes val and sets self.val, self.next, and self.random to None. Then create three nodes named node1, node2, and node3 with values 1, 2, and 3 respectively. Link them using next pointers: node1.next = node2 and node2.next = node3. Set node1.random = node3, node2.random = node1, and node3.random = node2.

DSA Python

# Define Node class and create linked list nodes
# Your code here

Hint

Start by defining the Node class with the required attributes. Then create three nodes and link them using next and random pointers as described.

2

Create a dictionary to map original nodes to their clones

Create an empty dictionary called old_to_new. Then create clones of each original node (node1, node2, node3) by calling Node(node.val) and store them in old_to_new with the original node as the key and the clone as the value.

DSA Python

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.random = None

node1 = Node(1)
node2 = Node(2)
node3 = Node(3)

node1.next = node2
node2.next = node3

node1.random = node3
node2.random = node1
node3.random = node2

# Create dictionary old_to_new and clone nodes
# Your code here

Hint

Create an empty dictionary and add entries for each original node with their cloned node as the value.

3

Set the next and random pointers for cloned nodes

Set the next pointer of each cloned node in old_to_new to the clone of the original node's next. Similarly, set the random pointer of each cloned node to the clone of the original node's random. For example, old_to_new[node1].next = old_to_new[node1.next] and old_to_new[node1].random = old_to_new[node1.random]. Do this for node1, node2, and node3.

DSA Python

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.random = None

node1 = Node(1)
node2 = Node(2)
node3 = Node(3)

node1.next = node2
node2.next = node3

node1.random = node3
node2.random = node1
node3.random = node2

old_to_new = {}
old_to_new[node1] = Node(node1.val)
old_to_new[node2] = Node(node2.val)
old_to_new[node3] = Node(node3.val)

# Set next and random pointers for cloned nodes
# Your code here

Hint

Use the dictionary to assign the next and random pointers of each cloned node by looking up the clones of the original nodes' pointers.

4

Print the cloned linked list showing values and random pointers

Create a variable cloned_head and set it to old_to_new[node1]. Then use a while loop to traverse the cloned list starting from cloned_head. In each iteration, print the current node's val and the val of its random pointer (or None if random is None) in the format: Node val: X, Random points to: Y. Move to the next node using current = current.next. Stop when current is None.

DSA Python

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.random = None

node1 = Node(1)
node2 = Node(2)
node3 = Node(3)

node1.next = node2
node2.next = node3

node1.random = node3
node2.random = node1
node3.random = node2

old_to_new = {}
old_to_new[node1] = Node(node1.val)
old_to_new[node2] = Node(node2.val)
old_to_new[node3] = Node(node3.val)

old_to_new[node1].next = old_to_new.get(node1.next)
old_to_new[node1].random = old_to_new.get(node1.random)
old_to_new[node2].next = old_to_new.get(node2.next)
old_to_new[node2].random = old_to_new.get(node2.random)
old_to_new[node3].next = old_to_new.get(node3.next)
old_to_new[node3].random = old_to_new.get(node3.random)

# Print cloned list nodes and their random pointers
# Your code here

Hint

Start from the cloned head node and loop through the list. For each node, print its value and the value of the node its random pointer points to. Use a conditional to handle None random pointers.