Python Program to Clone a Linked List with Random Pointers

Overview

This Python program clones a singly linked list where each node has two pointers: one pointing to the next node and another called random, which can point to any node in the list (or be null). The program duplicates the entire list, ensuring that the next and random pointers are preserved.

Program Explanation

The structure of the program includes a Node class to represent a node in the linked list, and a function to clone the linked list with both next and random pointers.

Steps Involved:

1. Create a class Node to represent the elements of the linked list. Each node has three attributes: data (the value of the node), next (pointer to the next node), and random (pointer to a random node).
2. Create a function clone_linked_list that takes the head of a linked list and returns the head of the cloned list.
3. The cloning process involves three steps:
   • Step 1: Insert a cloned node right after each original node in the list. This new node will have the same value as the original node.
   • Step 2: Set the random pointers of the cloned nodes. Each cloned node’s random pointer is set to the clone of the original node’s random pointer.
   • Step 3: Separate the cloned nodes from the original list to form the new cloned list.

Python Code


class Node:
"""
Node class to represent a linked list node with random pointers.
Each node contains the data, a pointer to the next node, and a pointer to a random node.
"""
def __init__(self, data):
self.data = data
self.next = None
self.random = None

def clone_linked_list(head):
“””
Clone a linked list with random pointers.

:param head: Head node of the original linked list
:return: Head node of the cloned linked list
“””
if not head:
return None

# Step 1: Create new nodes and insert them after each original node
current = head
while current:
new_node = Node(current.data)
new_node.next = current.next
current.next = new_node
current = new_node.next

# Step 2: Assign random pointers to the cloned nodes
current = head
while current:
if current.random:
current.next.random = current.random.next
current = current.next.next

# Step 3: Separate the cloned list from the original list
current = head
cloned_head = head.next
cloned_current = cloned_head

while current:
current.next = current.next.next
if cloned_current.next:
cloned_current.next = cloned_current.next.next
current = current.next
cloned_current = cloned_current.next

return cloned_head

# Helper function to print a linked list with random pointers
def print_linked_list_with_random(head):
“””
Print the elements of a linked list starting from the head node.
Each node’s random pointer is printed along with its data.

:param head: Head node of the linked list
“””
current = head
while current:
random_data = current.random.data if current.random else “None”
print(f”Node: {current.data}, Random: {random_data}”)
current = current.next
print()

# Example usage:
# Create a linked list:
# 1 -> 2 -> 3 -> None, with random pointers
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)

head.random = head.next.next # 1’s random points to 3
head.next.random = head # 2’s random points to 1
head.next.next.random = head.next # 3’s random points to 2

print(“Original Linked List:”)
print_linked_list_with_random(head)

# Clone the list
cloned_list = clone_linked_list(head)

print(“Cloned Linked List:”)
print_linked_list_with_random(cloned_list)

Program Explanation

This Python program defines the following:

• Node class: Each node in the linked list contains a value (data), a reference to the next node (next), and a reference to a random node (random).
• clone_linked_list function: This function clones a linked list by:
  • First, inserting cloned nodes right after each original node.
  • Second, setting up the random pointers for the cloned nodes.
  • Finally, separating the original and cloned nodes into two distinct linked lists.
• print_linked_list_with_random function: A utility function to display the linked list (both original and cloned) along with their random pointers.

Example Output

Given the original linked list:

• Node 1 (random -> 3)
• Node 2 (random -> 1)
• Node 3 (random -> 2)

The cloned linked list will be:

• Node 1 (random -> 3)
• Node 2 (random -> 1)
• Node 3 (random -> 2)