Deep clone random point singly list

December 16, 2023

medium

linkedlist

Problem #

Given the head to a singly linked list, where each node also has a “random” pointer that points to anywhere in the linked list, deep clone the list.

Solution 1 #

class ListNode:
    def __init__(self, value=0, next=None, random=None):
        self.value = value
        self.next = next
        self.random = random

def deep_clone(head):
    """
    Deep clone a linked list where each node has a 'next' pointer and a 'random' pointer.
    :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 a new node for each node in the original list and insert it between the original node and its next node
    current = head
    while current:
        new_node = ListNode(current.value, current.next)
        current.next = new_node
        current = new_node.next

    # Step 2: Update the random pointers for the new nodes
    current = head
    while current:
        if current.random:
            current.next.random = current.random.next
        current = current.next.next

    # Step 3: Separate the original list and the cloned list
    original = head
    clone = head.next
    clone_head = head.next
    while original:
        original.next = original.next.next
        if clone.next:
            clone.next = clone.next.next
        original = original.next
        clone = clone.next

    return clone_head

# Example usage:
# Creating a simple linked list with random pointers
# Node1 -> Node2 -> Node3
# Random pointers: Node1 -> Node3, Node2 -> Node1, Node3 -> Node2

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

node1.next = node2
node2.next = node3

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

# Cloning the list
cloned_head = deep_clone(node1)

# Verifying the cloned list (by printing values and random pointers)
current = cloned_head
while current:
    random_val = current.random.value if current.random else None
    print(f"Node Value: {current.value}, Random Value: {random_val}")
    current = current.next

Solution 1 Analysis: Step by Step #

The provided Python code performs a deep clone of a singly linked list where each node has two pointers: a ’next’ pointer (pointing to the next node in the list) and a ‘random’ pointer (pointing to any node in the list). The cloning process is done in three main steps:

Step 1: Interweaving Clone Nodes #

First, the code creates a new clone node for each original node and interweaves these cloned nodes with the original nodes. This is done by iterating through the original list, creating a new node for each existing node, and inserting this new node directly after its corresponding original node.

For example, if the original list is A -> B -> C, after this step, it becomes A -> A' -> B -> B' -> C -> C', where A', B', and C' are the new cloned nodes.

Step 2: Updating Random Pointers #

Next, the code updates the ‘random’ pointers in the cloned nodes. Since each cloned node is placed immediately after its original counterpart, the cloned node’s ‘random’ pointer should point to the clone of the original node’s ‘random’ target. This step is achieved by iterating through the list again, this time setting each cloned node’s ‘random’ pointer to the node after the ‘random’ target of the original node.

Step 3: Separating the Two Lists #

Finally, the original and cloned lists are separated. This is done by iterating through the interweaved list and adjusting the ’next’ pointers to skip the cloned nodes in the original list and skip the original nodes in the cloned list. This results in two separate lists: the original list in its initial state, and a new cloned list that is a deep copy of the original.

Example Usage #

The example creates a simple linked list where each node points to the next and also has a ‘random’ pointer to another node in the list. After cloning this list using deep_clone, the cloned list maintains the structure of the original list, including the ‘random’ connections.

The final part of the code prints out the values of each node in the cloned list and the values of their ‘random’ pointers, verifying that the deep clone was successful.

Solution 2 #

class ListNode:
    def __init__(self, value=0, next=None, random=None):
        self.value = value
        self.next = next
        self.random = random

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

    # Step 1: Create a mapping from original nodes to their clones
    current = head
    clone_map = {}
    while current:
        clone_map[current] = ListNode(current.value)
        current = current.next

    # Step 2: Set the next and random pointers for the cloned nodes
    current = head
    while current:
        if current.next:
            clone_map[current].next = clone_map[current.next]
        if current.random:
            clone_map[current].random = clone_map[current.random]
        current = current.next

    return clone_map[head]

# Example usage with the same list structure as before
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)

node1.next = node2
node2.next = node3

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

# Cloning the list
cloned_head = deep_clone(node1)

# Verifying the cloned list
current = cloned_head
while current:
    random_val = current.random.value if current.random else None
    print(f"Node Value: {current.value}, Random Value: {random_val}")
    current = current.next