Python Program to Clone a Linked List with Random Pointers

This Python program demonstrates how to create a linked list where each node has two pointers: next, which points to the next node in the sequence, and random, which points to any node in the list or none at all. The program then clones this linked list, including the random pointers, using an efficient approach that maintains O(n) time complexity and O(1) space complexity, where n is the number of nodes in the list.

Python Code

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

def clone_list(head):
    if not head:
        return None

    # Step 1: Create a new node for each existing node and link them together
    curr = head
    while curr:
        new_node = Node(curr.val)
        new_node.next = curr.next
        curr.next = new_node
        curr = new_node.next

    # Step 2: Assign random pointers for the copied nodes
    curr = head
    while curr:
        if curr.random:
            curr.next.random = curr.random.next
        curr = curr.next.next

    # Step 3: Separate the original list and the cloned list
    curr = head
    copy_head = head.next
    while curr:
        copy = curr.next
        curr.next = copy.next
        curr = curr.next
        if copy.next:
            copy.next = copy.next.next

    return copy_head

Explanation

The program defines a Node class representing each node in the linked list. The clone_list function performs the cloning operation in three main steps:

1. Iterating through the original list and inserting a cloned node just after each original node.
2. Correctly assigning the random pointers for the clone nodes by using the original node’s random pointers.
3. Restoring the original list and separating the cloned nodes to form the final cloned linked list.

This approach avoids the use of extra space for a hash table that would typically be used to map original nodes to their clones.