MEDIUM
DATA STRUCTURES AND ALGORITHMS

# How to Copy a List with Random Pointers: Interview Guide in Python, Java & C++

Written By Tom Wagner Carlos Wang

## An Overview of the Copy List With Random Pointers Problem

The Copy List With Random Pointers problem involves creating a deep copy of a linked list whose nodes point to random nodes within the list. Given this unique feature, the original linked list is challenging to traverse while building a new list in parallel. This problem demands careful use of pointers and can be solved with both a two-pass and a single-pass approach.

## An Example of the Copy List With Random Pointers Interview Question

Given a linked list with nodes that have an additional pointer referring to another node in the list, return a deep copy of the list. Node definition:

``````class Node:
def __init__(self, value: int, next: 'Node'=None, random: 'Node'=None):
self.value = value
self.next = next
self.random = random
`````` Input: head = [[5, Null], [13, 0], [7, 2], [13, 2]]

Output: new_head = [[5, Null], [13, 0], [7, 2], [13, 2]]

Note: Purely for the purposes of describing the list in text rather than a diagram, each node is represented by a tuple of `[value, index_of_random_node]`, where `value` is an integer and `index_of_random_node` is the index of the node referred to by the `random` pointer. Using the index allows us to distinguish between the two nodes with 13 as `value`'s because the constraints do not stipulate that `value`'s are unique.

Constraints
The number of nodes in the list is the range `[0, 10,000]`
`-10,000 <= Node.value <= 10,000`

## How to Copy a List With Random Pointers (Solutions in Java and Python)

### Approach 1: Two Passes

Without the `random` pointers, it is fairly straightforward to clone a linked list. New nodes can be created and linked via the `next` pointers as the given linked list is traversed. To traverse the list, a temporary pointer is used in a loop that sets the pointer to the next node until the pointer reaches `null`.

When `random` pointers are added and we traverse the list visiting both `next` and `random` pointers simultaneously, the destination node for a given `random` node might not exist yet in the copied list. We can work around this limitation by creating all the nodes required for our deep copy first and then linking them later.

We can work around this limitation by creating all the nodes required for our deep copy first and then linking them later. In the first traversal, we create new nodes using the value in the original node. We save a mapping from the original node to the new node in a hash table. In the second pass, link the nodes of the new list by connecting the `next` and `random` pointers, finding the destination nodes in the hash table as we go.

#### Copy List With Random Pointers Python Solution - Two Passes

``````def deep_copy(head: Optional[Node]) -> Optional[Node]:
return None

hash_table: dict[Node, Node] = {}

# 1st pass: copy the nodes and store the mapping
while p:
hash_table[p] = Node(p.value)
p = p.next

# 2nd pass: connect the newly created nodes
while p:
p_new = hash_table[p]
if p.next:
p_new.next = hash_table[p.next]
if p.random:
p_new.random = hash_table[p.random]

p = p.next

#### Time/Space Complexity

• Time complexity: `O(n)`
• Space complexity: `O(n)` - extra space is needed for the initial copy.

Nodes are mapped from original to new list in a dictionary, which also scales linearly with list size.

### Approach 2: One Pass

In the first approach, we separated the creation and linking of the nodes because the `random` pointer may refer to a node that hasn't yet been created. Instead of waiting until all nodes are created for the replica list, we could alternatively create any missing nodes proactively and avoid a second traversal.

To achieve this, we initialize the hash table with the head node and its copy. Using a temporary pointer to iterate through the original list, we first check if the `next` and `random` nodes are mapped to their copies in the hash table. If they don't already exist, they are created immediately and added to the hash table. Then, the copied node can be linked to both its `next` and `random` nodes without waiting.

#### Copy List With Random Pointers Python Solution - One Pass

``````def deep_copy(head: Optional[Node]) -> Optional[Node]:
return None

while p:
if p.next:
if p.next not in hash_table:
hash_table[p.next] = Node(p.next.value)
hash_table[p].next = hash_table[p.next]
if p.random:
if p.random not in hash_table:
hash_table[p.random] = Node(p.random.value)
hash_table[p].random = hash_table[p.random]

p = p.next
``````

#### Time/Space Complexity

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

The list is traversed once and the hash table contains mappings from each node to its copy.

## Practice the Copy List With Random Pointers Problem With Our AI Interviewer

Start AI Interview

## Copy List With Random Pointers Frequently Asked Questions (FAQ)

### What is a deep copy of a linked list?

To perform a deep copy on a linked list means to create a new linked list with new nodes that have the same values and references as the original list. The copied list is structurally identical to the original list, but the nodes are separate entities in memory, and any references to other nodes (e.g., next and random pointers) need to be copied to the new node. Deep copying a linked list can be more complex than simply creating a new list and copying the values, especially if the list contains random pointers or if there are cycles within the list.

### How do you randomize a linked list?

To randomize a linked list, we can follow these steps. First, traverse the linked list to count the total number of nodes. Then, generate a random number within the range of the node count. Next, we traverse the linked list again and stop at the node corresponding to the randomly generated index. We remove this node from the original linked list. These steps of generating a random index and removing the node are repeated until all nodes have been removed. The next phase is to create a new linked list by inserting the removed nodes at random positions in the new list, effectively randomizing their order.

### How do you clone a linked list with a random pointer?

Cloning a linked list with a random pointer involves creating an identical copy of the original linked list while preserving the random connections between nodes. To accomplish this, we traverse the original list and create a new node for each encountered node, assigning the same data value. Simultaneously, we create a mapping between the original nodes and their corresponding new nodes. Then, we traverse the list again and set the next pointer of each new node to the new node corresponding to the next node in the original list. Finally, we traverse the list once more and set the random pointer of each new node the random node from the original list using the mapping we created earlier.