# Deep clone random point singly list

##### December 16, 2023

## 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
```