Technical Interview Question: Singly Linked Lists - Copy List with Random Pointer

You are given a linked list where each node has a random pointer that points to any other node in the linked list or null. Your task is to make a deep copy of the linked list, creating a new list and linking the nodes in the same order as the original list. The random pointers in the new list should also point to the corresponding new nodes.

For example, given the following linked list:

Original: 1 -> 2 -> 3 -> 4
                   ↘    ↗
                    2 <- 4

The deep copy should result in the following linked list:

New:      1 -> 2 -> 3 -> 4
                     ↘    ↗
                      2 <- 4

Write a function copyRandomList that takes the head of the original linked list as an input and returns the head of the new linked list.

Function Signature: Node copyRandomList(Node head)

Input

• head: The head of the original linked list. It is guaranteed to be a non-empty linked list.

Output

• The head of the copied linked list.

Note

• The linked list nodes are of type Node and are defined as:

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

• The values of the nodes in the linked list are unique and between 1 and 10^5.

Constraints:

• The number of nodes in the linked list is in the range [1, 1000].

Example

Input:

Original: 1 -> 2 -> 3 -> 4
                   ↘    ↗
                    2 <- 4

Output:

New:      1 -> 2 -> 3 -> 4
                     ↘    ↗
                      2 <- 4

Explanation:

• In the original linked list, the random pointers of node 3 and node 4 point to node 2.
• In the new linked list, the random pointers of the corresponding nodes should also point to the corresponding new nodes.

Solution

To create a deep copy of a linked list with random pointers, we need to perform the following steps:

1. Iterate through the original linked list and create a copy of each node by inserting it after the original node.
2. Set the random pointers of the new nodes to the corresponding new nodes.
3. Separate the new linked list from the original linked list by updating the next pointers of the original nodes and the new nodes.
4. Return the head of the new linked list.

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head:
            return None
        
        # Step 1: Create a copy of each node and insert it after the original node
        curr = head
        while curr:
            new_node = Node(curr.val)
            new_node.next = curr.next
            curr.next = new_node
            curr = curr.next.next
        
        # Step 2: Set the random pointers of the new nodes to the corresponding new nodes
        curr = head
        while curr:
            if curr.random:
                curr.next.random = curr.random.next
            curr = curr.next.next
        
        # Step 3: Separate the new linked list from the original linked list
        curr = head
        new_head = head.next # Head of the new linked list
        new_curr = new_head
        while curr:
            curr.next = curr.next.next
            if new_curr.next:
                new_curr.next = new_curr.next.next
            curr = curr.next
            new_curr = new_curr.next
        
        # Step 4: Return the head of the new linked list
        return new_head

The time complexity of this solution is O(N) and the space complexity is O(1), where N is the number of nodes in the original linked list.