Copy List with Random Pointer in Python (O(n) Time Complexity)

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y.

Return the head of the copied linked list.

The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

val: an integer representing Node.val
random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.

Your code will only be given the head of the original linked list.

Example 1:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Example 3:

Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

Example 4:

Input: head = []
Output: []
Explanation: The given linked list is empty (null pointer), so return null.

Constraints:

0 <= n <= 1000
-10000 <= Node.val <= 10000
Node.random is null or is pointing to some node in the linked list.

Note:

Your algorithm should run in O(n) time and use at most O(n) extra space.

Understanding the Problem

The core challenge of this problem is to create a deep copy of a linked list where each node has an additional random pointer. The deep copy should be a completely new list with no shared nodes with the original list. This problem is significant in scenarios where data structures need to be duplicated without affecting the original structure, such as in undo operations, cloning complex objects, etc.

Approach

To solve this problem, we can use a three-step approach:

Interweaving the original list with copied nodes: Create new nodes and insert them right next to their corresponding original nodes.
Assigning random pointers: Set the random pointers of the new nodes using the interwoven structure.
Restoring the original list and extracting the copied list: Separate the interwoven list into the original and the copied list.

Algorithm

Let's break down the algorithm step-by-step:

Traverse the original list and create new nodes. Insert each new node right after its corresponding original node.
Traverse the interwoven list and set the random pointers for the new nodes. If the original node's random pointer points to a node, the new node's random pointer should point to the node right after the original node's random pointer.
Separate the interwoven list into the original list and the copied list by adjusting the next pointers.

Code Implementation

class Node:
    def __init__(self, val: int, next: 'Node' = None, random: 'Node' = None):
        self.val = val
        self.next = next
        self.random = random

def copyRandomList(head: 'Node') -> 'Node':
    if not head:
        return None

    # Step 1: Create new nodes and interweave them with the original nodes
    current = head
    while current:
        new_node = Node(current.val, current.next)
        current.next = new_node
        current = new_node.next

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

    # Step 3: Separate the interwoven list into original and copied lists
    current = head
    new_head = head.next
    while current:
        new_node = current.next
        current.next = new_node.next
        if new_node.next:
            new_node.next = new_node.next.next
        current = current.next

    return new_head

Complexity Analysis

The time complexity of this algorithm is O(n) because we traverse the list a constant number of times. The space complexity is also O(n) due to the space required for the new nodes.

Edge Cases

Consider the following edge cases:

An empty list (head is null): The function should return null.
A list with only one node: The function should correctly handle the random pointer, whether it is null or points to itself.

Testing

To test the solution comprehensively, consider the following test cases:

def test_copyRandomList():
    # Test case 1: Empty list
    assert copyRandomList(None) == None

    # Test case 2: Single node with no random pointer
    node1 = Node(1)
    assert copyRandomList(node1).val == 1

    # Test case 3: Single node with random pointer to itself
    node1.random = node1
    copied = copyRandomList(node1)
    assert copied.val == 1
    assert copied.random == copied

    # Test case 4: Multiple nodes with random pointers
    node1 = Node(1)
    node2 = Node(2)
    node1.next = node2
    node1.random = node2
    node2.random = node2
    copied = copyRandomList(node1)
    assert copied.val == 1
    assert copied.random.val == 2
    assert copied.next.val == 2
    assert copied.next.random.val == 2

test_copyRandomList()

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

Break down the problem into smaller, manageable steps.
Think about how to maintain the relationships between nodes while creating new nodes.
Use diagrams to visualize the list structure and the changes you need to make.

Conclusion

Understanding and solving the "Copy List with Random Pointer" problem helps in mastering deep copy concepts and linked list manipulations. Practice similar problems to improve your problem-solving skills.