Copy List with Random Pointer

Medium

Amazon

3 views

Topics:

Linked Lists

A linked list 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.

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]]

Can you provide a solution with O(1) space complexity?

Copy List with Random Pointer

Medium

Amazon

3 views

Topics:

Linked Lists

A linked list 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.

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]]

Can you provide a solution with O(1) space complexity?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the random pointer ever point to a node that appears earlier in the list than the current node?
What is the range of possible values within the nodes of the linked list?
Is it possible for the input list to be null or empty?
If a random pointer points to null in the original list, should the corresponding random pointer in the copied list also point to null?
Is the linked list singly linked, as the problem description implies?

Brute Force Solution

Approach

We want to create an exact duplicate of a linked list, but this list has a twist: each item can point to any other item in the list randomly. The brute force way to do this is to painstakingly rebuild the list item by item, making sure each item in the copy has the same relationships as the original.

Here's how the algorithm would work step-by-step:

First, create a brand new item that mirrors the first item in the original list, copying its value.
Then, create a new item that mirrors the second item in the original list, copying its value.
Continue creating new items until you have a new item for every item in the original list.
Now, go back to the beginning of the original list. For the first item, find which item its random pointer points to.
In your new list, make the first item's random pointer point to the corresponding new item that you created in step 2 that mirrors what the original random pointer was pointing to.
Repeat this process for every item in the original list: find where its random pointer goes, and then make the corresponding item in the new list point to the corresponding duplicate item.
Once you've done this for every item, your new list will be an exact duplicate of the original, including all the random pointers.

Code Implementation

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None
        self.random = None

def copy_list_with_random_pointer_brute_force(head):
    if not head:
        return None

    # Create a dictionary to store the mapping between original nodes and copied nodes
    original_to_copy_map = {}

    # First pass: Create new nodes with the same values as the original list
    current_node = head
    while current_node:
        copy_node = Node(current_node.value)
        original_to_copy_map[current_node] = copy_node
        current_node = current_node.next

    # Second pass: Set the next and random pointers of the new nodes
    current_node = head
    while current_node:
        copy_node = original_to_copy_map[current_node]

        # Set the next pointer of the copy node
        if current_node.next:
            copy_node.next = original_to_copy_map[current_node.next]

        # Now handle the random pointers
        if current_node.random:
            copy_node.random = original_to_copy_map[current_node.random]

        current_node = current_node.next

    # Return the head of the copied list
    return original_to_copy_map[head]

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through the original list of n nodes once to create n new nodes. Then, for each of the n nodes in the original list, it potentially iterates through the entire new list (of size n) to find the corresponding node to which the random pointer should point. This results in a nested loop structure where we have approximately n operations inside another n operations leading to n * n total operations, which simplifies to O(n²).

Space Complexity

O(N) – The provided approach creates a new node for every node in the original list. This means a new list of N nodes is generated, where N is the number of nodes in the original list. Additionally, storing the mappings between old and new nodes described in steps 4-6 may involve an implicit data structure such as a hash map. Thus, the auxiliary space used scales linearly with the number of nodes in the original list, N.

Optimal Solution

Approach

To create a perfect copy, we use a clever trick to avoid repeated lookups. We first weave the copy into the original list, then fix the 'random' connections, and finally separate the copy from the original.

Here's how the algorithm would work step-by-step:

First, for each item in the original list, create a new copy of that item and place it directly after the original in the list. This effectively doubles the list's length, with each original node followed by its copy.
Next, go through the modified list. For each copy you made, look at the item its corresponding original item points to with its 'random' pointer. Point the copy's 'random' pointer to the copy of that 'random' item. Because each original item has its copy right next to it, finding the correct copy is easy.
Finally, separate the original list from the copied list. This step involves re-linking the original list to its original structure and creating a new, independent list of the copies. You now have a complete copy of the original list, including all its random connections.

Code Implementation

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None
        self.random = None

def copy_list_with_random_pointer(head):
    if not head:
        return None

    current_node = head
    # Interweave copied nodes within the original list.
    while current_node:
        copied_node = Node(current_node.value)
        copied_node.next = current_node.next
        current_node.next = copied_node
        current_node = copied_node.next

    current_node = head

    # Assign random pointers for the copied nodes.
    while current_node:
        if current_node.random:
            current_node.next.random = current_node.random.next
        current_node = current_node.next.next

    current_node = head
    copied_head = head.next
    copied_node = copied_head

    # Separate the copied list from the original list.
    while current_node:
        current_node.next = current_node.next.next
        if copied_node.next:
            copied_node.next = copied_node.next.next

        current_node = current_node.next
        copied_node = copied_node.next

    return copied_head

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the linked list three times. First, it iterates through the original list of n nodes to create a copy of each node and insert it after the original (this step takes O(n) time). Second, it iterates through the augmented list of 2n nodes to assign the random pointers of the copied nodes (this step takes O(n) time because each random pointer assignment is a constant-time operation). Finally, it iterates through the augmented list again to separate the original and copied lists (again O(n) time). Since all steps are linear and sequential, the overall time complexity is O(n) + O(n) + O(n) which simplifies to O(n).

Space Complexity

O(1) – The provided solution modifies the original list in place and creates a new list by weaving copies into the original list structure. No auxiliary data structures like hash maps or additional lists are used to store intermediate results or track visited nodes. The operations involve only pointer manipulation and temporary variable assignments, which require a constant amount of extra space regardless of the number of nodes (N) in the original list. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty input list	Return null immediately as there's nothing to copy.
Single node list	The solution should correctly copy the single node and its random pointer (which might be null or point to itself).
List with all random pointers being null	The copied list should also have all random pointers as null.
List where all random pointers point to the same node	The copied list should have all random pointers pointing to the copied version of that node.
Random pointer creates a cycle within the original list	The copying mechanism should not enter an infinite loop and must correctly handle the cyclic random pointer.
Large list to test memory usage and performance	The solution should be memory efficient, ideally O(n) space, and should avoid stack overflow issues in recursive implementations by using iterative approaches.
Random pointer points to itself	The copy's random pointer should point to the copy of the node itself.
Original list is modified during the copying process (though not usually expected in interview context).	The copying process should be independent of modifications to the original list during its execution, which suggests making a complete copy right away.