# 1. Introduction

"Copy List with Random Pointer" is a challenging problem that requires deep understanding of linked list manipulation, particularly when dealing with complex node relationships. This problem involves creating a deep copy of a linked list where each node contains an extra pointer to any random node in the list or null. The complexity arises in accurately replicating both the *next* and *random* pointers of the original list in the new copy.

## Problem

Given a linked list where each node contains an additional random pointer, the task is to construct a deep copy of the list. The deep copy should consist of exactly *n* brand new nodes, and each new node should have its value set to the value of its corresponding original node. The *next* and *random* pointers of the new nodes should accurately reflect the relationships in the original list, without any pointers in the new list pointing to nodes in the original list.

# 2. Solution Steps

1. Iterate through the original list and create a copy of each node, placing the copy next to its original node.

2. Iterate through the list again to set up the *random* pointers in the copied nodes.

3. Separate the original list and the copied list, fixing the *next* pointers.

4. Return the head of the copied list.

# 3. Code Program

```
class Node:
def __init__(self, val=0, next=None, random=None):
self.val = val
self.next = next
self.random = random
def copyRandomList(head):
if not head:
return None
# Step 1: Create copied nodes next to original ones
current = head
while current:
next_node = current.next
current.next = Node(current.val, next_node)
current = next_node
# Step 2: Set up random pointers in the copied nodes
current = head
while current:
if current.random:
current.next.random = current.random.next
current = current.next.next
# Step 3: Separate the two lists
original = head
copy = head.next
copy_head = head.next
while original:
original.next = original.next.next
copy.next = copy.next.next if copy.next else None
original = original.next
copy = copy.next
return copy_head
# Example Usage
# Creating a list with random pointers for demonstration
node1 = Node(1)
node2 = Node(2)
node1.next = node2
node1.random = node2
node2.random = node1
copied_head = copyRandomList(node1)
# Output the list
output = []
current = copied_head
while current:
output.append(f"Node({current.val}, Random({current.random.val if current.random else 'None'}))")
current = current.next
print(output)
```

### Output:

['Node(1, Random(2))', 'Node(2, Random(1))']

### Explanation:

**1. Node Class**: The *Node* class represents each node in the linked list with *val*, *next*, and *random* attributes.

**2. Copying Nodes**: Each node in the original list is copied and placed next to its original node.

**3. Setting Random Pointers**: The *random* pointers of the copied nodes are set by referencing the original node's *random* pointer.

**4. Separating Lists**: The original and copied lists are separated by adjusting the *next* pointers.

**5. Deep Copy**: The approach ensures a deep copy of the list, with no pointers in the new list referencing nodes in the original list.

**6. Result**: The function returns the head of the copied list with an accurate replication of the *next* and *random* pointers.

## Comments

## Post a Comment