We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Copy List with Random Pointer

Difficulty: Medium

Problem Description

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.

Key Insights

  • Each node in the linked list has two pointers: next and random.
  • A deep copy requires creating new nodes while preserving the structure of the original list.
  • We can use a hash table (dictionary) to map original nodes to their corresponding copied nodes for easy reference.
  • The problem can be solved in one pass to create copies and another pass to set the random pointers.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve this problem, we can use a hash table to keep track of the mapping between original nodes and their corresponding copied nodes. The algorithm consists of the following steps:

  1. Create a copy of each node and store it in the hash table.
  2. Iterate through the original list to set the next and random pointers of the copied nodes using the mapping in the hash table.
  3. Return the head of the new copied list.

Code Solutions

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

def copyRandomList(head):
    if not head:
        return None
    
    # Step 1: Create a copy of each node and store it in a hash table
    old_to_new = {}
    current = head
    while current:
        old_to_new[current] = Node(current.val)
        current = current.next
    
    # Step 2: Set the next and random pointers for copied nodes
    current = head
    while current:
        if current.next:
            old_to_new[current].next = old_to_new[current.next]
        if current.random:
            old_to_new[current].random = old_to_new[current.random]
        current = current.next
    
    # Return the head of the copied list
    return old_to_new[head]
← Back to All Questions