Copy List with Random Pointer

Medium

Google

1 view

Topics:

Linked Lists

You are given the head of a singly linked list where each node has two pointers: next and random. The next pointer is the same as always, while the random pointer can point to any node in the list, or it can be null. Your task is to create a deep copy of this linked list.

A deep copy means that you need to create entirely new nodes with the same values as the original list. The next and random pointers of the new nodes should point to the corresponding new nodes in the copied list, mirroring the structure of the original list. Crucially, no pointers in the new list should point to any nodes in the original list.

For instance, consider this example:

Original list: A -> B -> C, where A.random points to C, and B.random points to A.

Your deep copy should create a new list: A' -> B' -> C', where A'.random points to C', and B'.random points to A'. A', B', and C' are brand new nodes. Modifying A, B, or C should not affect A', B', or C', and vice versa.

Here are some important considerations:

Empty list: What should you return if the input list is empty?
Single node: How does your solution handle a list with only one node?
Random pointers: How do you ensure the random pointers in the new list correctly point to the new nodes in the copied list, and not the old ones?

Can you provide an algorithm and code to perform a deep copy of this linked list, and what is the time and space complexity of your approach?

Copy List with Random Pointer

Medium

Google

1 view

Topics:

Linked Lists

For instance, consider this example:

Original list: A -> B -> C, where A.random points to C, and B.random points to A.

Here are some important considerations:

Empty list: What should you return if the input list is empty?
Single node: How does your solution handle a list with only one node?
Random pointers: How do you ensure the random pointers in the new list correctly point to the new nodes in the copied list, and not the old ones?

Can you provide an algorithm and code to perform a deep copy of this linked list, and what is the time and space complexity of your approach?

Solution

Deep Copy of a Linked List with Random Pointers

Problem Description

Given a linked list where each node has a next pointer and a random pointer (which can point to any node or null), create a deep copy of the list.

Naive Approach (Brute Force)

Create New Nodes: Iterate through the original list and create new nodes with the same values as the original nodes. Store the mapping between original nodes and new nodes in a dictionary (hash map).
Set Next Pointers: Iterate through the original list again. For each original node, set the next pointer of its corresponding new node to the new node corresponding to the original node's next pointer.
Set Random Pointers: Iterate through the original list one more time. For each original node, set the random pointer of its corresponding new node to the new node corresponding to the original node's random pointer.

Code (Python)

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

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

    # Create a mapping from original nodes to new nodes
    node_map = {}
    curr = head
    while curr:
        node_map[curr] = Node(curr.val)
        curr = curr.next

    # Set next pointers
    curr = head
    while curr:
        if curr.next:
            node_map[curr].next = node_map[curr.next]
        curr = curr.next

    # Set random pointers
    curr = head
    while curr:
        if curr.random:
            node_map[curr].random = node_map[curr.random]
        curr = curr.next

    return node_map[head]

Time Complexity

O(n), where n is the number of nodes in the linked list (three iterations).

Space Complexity

O(n), to store the mapping between original nodes and new nodes in the dictionary.

Optimal Approach (Using Interweaving)

This approach optimizes the space complexity by avoiding the use of a separate hash map.

Interweave Nodes: Iterate through the original list and create a new node after each original node. Insert the new node right after the original node.
Set Random Pointers: Iterate through the modified list. For each new node, set its random pointer to the copy of the node pointed to by the original node's random pointer.
Separate Lists: Separate the original list and the copied list by adjusting the next pointers.

Code (Python)

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

    # Interweave the new nodes
    curr = head
    while curr:
        new_node = Node(curr.val)
        new_node.next = curr.next
        curr.next = new_node
        curr = new_node.next

    # Set random pointers for the new nodes
    curr = head
    while curr:
        if curr.random:
            curr.next.random = curr.random.next
        curr = curr.next.next

    # Separate the lists
    curr = head
    new_head = head.next
    new_curr = new_head

    while curr:
        curr.next = new_curr.next
        curr = curr.next
        if curr:
            new_curr.next = curr.next
            new_curr = new_curr.next
        else:
            new_curr.next = None

    return new_head

Time Complexity

O(n), where n is the number of nodes in the linked list (three iterations).

Space Complexity

O(1), constant extra space.

Edge Cases

Empty List: If the input list is empty (head is None), return None.
Single Node: If the list contains only one node, create a copy of that node and return it.
Random Pointer Points to Null: Handle the case where the random pointer of a node is null.
Cycles: Although not explicitly stated, it's good to consider if the original list has cycles. The given solutions work correctly even if there are cycles present because the deep copy creates completely new nodes.

Solution

Deep Copy of a Linked List with Random Pointers

Problem Description

Given a linked list where each node has a next pointer and a random pointer (which can point to any node or null), create a deep copy of the list.

Naive Approach (Brute Force)

Create New Nodes: Iterate through the original list and create new nodes with the same values as the original nodes. Store the mapping between original nodes and new nodes in a dictionary (hash map).
Set Next Pointers: Iterate through the original list again. For each original node, set the next pointer of its corresponding new node to the new node corresponding to the original node's next pointer.
Set Random Pointers: Iterate through the original list one more time. For each original node, set the random pointer of its corresponding new node to the new node corresponding to the original node's random pointer.

Code (Python)

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

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

    # Create a mapping from original nodes to new nodes
    node_map = {}
    curr = head
    while curr:
        node_map[curr] = Node(curr.val)
        curr = curr.next

    # Set next pointers
    curr = head
    while curr:
        if curr.next:
            node_map[curr].next = node_map[curr.next]
        curr = curr.next

    # Set random pointers
    curr = head
    while curr:
        if curr.random:
            node_map[curr].random = node_map[curr.random]
        curr = curr.next

    return node_map[head]

Time Complexity

O(n), where n is the number of nodes in the linked list (three iterations).

Space Complexity

O(n), to store the mapping between original nodes and new nodes in the dictionary.

Optimal Approach (Using Interweaving)

This approach optimizes the space complexity by avoiding the use of a separate hash map.

Interweave Nodes: Iterate through the original list and create a new node after each original node. Insert the new node right after the original node.
Set Random Pointers: Iterate through the modified list. For each new node, set its random pointer to the copy of the node pointed to by the original node's random pointer.
Separate Lists: Separate the original list and the copied list by adjusting the next pointers.

Code (Python)

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

    # Interweave the new nodes
    curr = head
    while curr:
        new_node = Node(curr.val)
        new_node.next = curr.next
        curr.next = new_node
        curr = new_node.next

    # Set random pointers for the new nodes
    curr = head
    while curr:
        if curr.random:
            curr.next.random = curr.random.next
        curr = curr.next.next

    # Separate the lists
    curr = head
    new_head = head.next
    new_curr = new_head

    while curr:
        curr.next = new_curr.next
        curr = curr.next
        if curr:
            new_curr.next = curr.next
            new_curr = new_curr.next
        else:
            new_curr.next = None

    return new_head

Time Complexity

O(n), where n is the number of nodes in the linked list (three iterations).

Space Complexity

O(1), constant extra space.

Edge Cases

Empty List: If the input list is empty (head is None), return None.
Single Node: If the list contains only one node, create a copy of that node and return it.
Random Pointer Points to Null: Handle the case where the random pointer of a node is null.
Cycles: Although not explicitly stated, it's good to consider if the original list has cycles. The given solutions work correctly even if there are cycles present because the deep copy creates completely new nodes.