# 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

return None

# Step 1: Create copied nodes next to original ones
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
while current:
if current.random:
current.next.random = current.random.next
current = current.next.next

# Step 3: Separate the two lists
while original:
original.next = original.next.next
copy.next = copy.next.next if copy.next else None
original = original.next
copy = copy.next

# 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
# Output the list
output = []
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.