Copy List with Random Pointer - Python Solution

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.