Copy Linked List with Random Pointer

Problem Statement

You are given the head of a linked list of length n. Unlike a singly linked list, each node contains an additional pointer random, which may point to any node in the list, or null.

Create a deep copy of the list.

The deep copy should consist of exactly n new nodes, each including:

  • The original value val of the copied node
  • A next pointer to the new node corresponding to the next pointer of the original node
  • A random pointer to the new node corresponding to the random pointer of the original node

Note: None of the pointers in the new list should point to nodes in the original list.

Return the head of the copied linked list.

In the examples, the linked list is represented as a list of n nodes. Each node is represented as a pair of [val, random_index] where random_index is the index of the node (0-indexed) that the random pointer points to, or null if it does not point to any node.

Example 1:

Input: head = [[3,null],[7,3],[4,0],[5,1]]


Output: [[3,null],[7,3],[4,0],[5,1]]

Example 2:

Input: head = [[1,null],[2,2],[3,2]]


Output: [[1,null],[2,2],[3,2]]

You should aim for a solution as good or better than O(n) time and O(n) space, where n is the length of the given list.

You should aim for a solution as good or better than O(n) time and O(n) space, where n is the length of the given list.

Hint 1

There is an extra random pointer for each node, and unlike the next pointer, which points to the next node, the random pointer can point to any random node in the list. A deep copy is meant to create completely separate nodes occupying different memory. Why can’t we build a new list while iterating through the original list?

Hint 2

Because, while iterating through the list, when we encounter a node and create a copy of it, we can’t immediately assign the random pointer’s address. This is because the random pointer might point to a node that has not yet been created. To solve this, we can first create copies of all the nodes in one iteration. However, we still can’t directly assign the random pointers since we don’t have the addresses of the copies of those random pointers. Can you think of a data structure to store this information? Maybe a hash data structure could help.

Hint 3

We can use a hash data structure, such as a hash map, which takes O(1) time to retrieve data. This can help by mapping the original nodes to their corresponding copies. This way, we can easily retrieve the copy of any node and assign the random pointers in a subsequent pass after creating copies of all nodes in the first pass.

Solution

Hash Map (Recursion)

"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""


def copy_random_list(head: 'Optional[Node]') -> 'Optional[Node]':
    node_map = {}


    def deep_copy(node):
        if node is None:
            return None
        if node in node_map:
            return node_map[node]


        copy = Node(node.val)
        node_map[node] = copy
        copy.next = deep_copy(node.next)
        copy.random = node_map.get(node.random)
        return copy


    return deep_copy(head)

Time complexity: O(n) Space complexity: O(n)

Hash Map (Two Pass)

"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""


def copy_random_list(head: 'Optional[Node]') -> 'Optional[Node]':
    old_to_copy = {None: None}


    curr = head
    while curr:
        copy = Node(curr.val)
        old_to_copy[curr] = copy
        curr = curr.next
    curr = head
    while curr:
        copy = old_to_copy[curr]
        copy.next = old_to_copy[curr.next]
        copy.random = old_to_copy[curr.random]
        curr = curr.next
    return old_to_copy[head]

Time complexity: O(n) Space complexity: O(n)

Hash Map (One Pass)

"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""


import collections


def copy_random_list(head: 'Optional[Node]') -> 'Optional[Node]':
    old_to_copy = collections.defaultdict(lambda: Node(0))
    old_to_copy[None] = None


    curr = head
    while curr:
        old_to_copy[curr].val = curr.val
        old_to_copy[curr].next = old_to_copy[curr.next]
        old_to_copy[curr].random = old_to_copy[curr.random]
        curr = curr.next
    return old_to_copy[head]

Time complexity: O(n) Space complexity: O(n)

Space Optimized - I

"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""


def copy_random_list(head: 'Optional[Node]') -> 'Optional[Node]':
    if head is None:
        return None


    l1 = head
    while l1 is not None:
        l2 = Node(l1.val)
        l2.next = l1.next
        l1.next = l2
        l1 = l2.next


    new_head = head.next


    l1 = head
    while l1 is not None:
        if l1.random is not None:
            l1.next.random = l1.random.next
        l1 = l1.next.next


    l1 = head
    while l1 is not None:
        l2 = l1.next
        l1.next = l2.next
        if l2.next is not None:
            l2.next = l2.next.next
        l1 = l1.next


    return new_head

Time complexity: O(n) Space complexity: O(1)

Space Optimized - II

"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""


def copy_random_list(head: 'Optional[Node]') -> 'Optional[Node]':
    if head is None:
        return None


    l1 = head
    while l1:
        l2 = Node(l1.val)
        l2.next = l1.random
        l1.random = l2
        l1 = l1.next


    new_head = head.random


    l1 = head
    while l1:
        l2 = l1.random
        l2.random = l2.next.random if l2.next else None
        l1 = l1.next


    l1 = head
    while l1 is not None:
        l2 = l1.random
        l1.random = l2.next
        l2.next = l1.next.random if l1.next else None
        l1 = l1.next


    return new_head

Time complexity: O(n) Space complexity: O(1)