How do you solve Copy List with Random Pointer?

Use a hash map that maps each original node to its copied node. First, iterate through the original list to create a copy of each node and store it in the map. Then, iterate again to assign the 'next' and 'random' pointers of each copied node by looking up the corresponding nodes in the map. Finally, return the copy corresponding to the original head. This approach guarantees O(n) time and space complexity.

What pattern does Copy List with Random Pointer use?

The Pattern: Hash Maps (Node Mapping for Deep Copy) The Heuristic: When copying complex linked structures with arbitrary pointers, maintain a hash map from original nodes to their copies to enable constant-time lookup and correct pointer assignment, transforming a potentially quadratic problem into a linear one.

Copy List with Random Pointer — Hash Maps

Q: What is the time complexity of Copy List with Random Pointer?

O(n). The algorithm performs two passes over the list of n nodes. Each pass is O(n), and hash map lookups and insertions are O(1) on average, resulting in overall O(n) time.

Problem

Given the head of a linked list where each node contains an additional random pointer which could point to any node in the list or null, return a deep copy of the list.

0 ≤ Number of nodes ≤ 1000
−10⁴ ≤ Node.val ≤ 10⁴
Node.random is null or points to a node in the linked list

Example

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]

Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

The input list has 5 nodes. The first node has value 7 and its random pointer is null. The second node has value 13 and its random pointer points to the first node (index 0). The third node has value 11 and its random pointer points to the fifth node (index 4). The fourth node has value 10 and its random pointer points to the third node (index 2). The fifth node has value 1 and its random pointer points to the first node (index 0). The algorithm creates a new list with new nodes having the same values and the same next and random pointer relationships, but no node is shared with the original list.

Approach

Straightforward Solution

A naive approach would be to copy nodes one by one and for each node, search the original list to find the target of its random pointer's copy. This leads to O(n^2) time complexity because for each node, locating the random pointer's copy requires a linear scan.

Core Observation

Each node in the original list must be copied exactly once, and the copied nodes must replicate the original 'next' and 'random' pointer structure. The random pointers can point arbitrarily, so a simple linear copy of 'next' pointers is insufficient. The key is to maintain a mapping from original nodes to their copies to correctly assign 'next' and 'random' pointers in the copied list.

Path to Optimal

Preview

The key recognition signals are 'deep copy', 'random pointer', and 'arbitrary pointer references'. These indicate the use of a hash map to store a mapping from original nodes to their copies…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use a hash map that maps each original node to its copied node. First, iterate through the original list to create a copy of each node and store it in the map…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

The algorithm performs two passes over the list of n nodes. Each pass is O(n), and hash map lookups and insertions are O(1) on average, resulting in overall O(n) time.

Space

O(n)

The hash map stores a mapping for each of the n nodes, requiring O(n) auxiliary space. This space is necessary to maintain the correspondence between original and copied nodes.

Solution

Python

1# Definition for a Node.
2# class Node:
3#     def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
4#         self.val = int(x)
5#         self.next = next
6#         self.random = random
7
8class Solution:
9    def copyRandomList(self, head: 'Node') -> 'Node':
10        if not head:
11            return None
12
13        old_to_copy = { None: None }
14
15        curr = head
16        while curr:
17            copy = Node(curr.val)
18            old_to_copy[curr] = copy
19            curr = curr.next
20        
21        curr = head
22        while curr:
23            copy = old_to_copy[curr]
24            copy.next = old_to_copy[curr.next]
25            copy.random = old_to_copy[curr.random]
26            curr = curr.next
27        
28        return old_to_copy[head]

Step-by-Step Solution

1

Handle Empty Input Before Starting the Deep Copy

10if not head:
11    return None

Objective

To exit immediately when the input head is null, since the deep copy of an empty list is also empty.

Key Insight

Handling the empty-list case up front avoids unnecessary map setup and traversal. It also keeps the two-pass copy logic focused on the non-empty case.

Interview Quick-Check

Core Logic

Return None immediately when head is null because an empty list copies to an empty list.

State & Boundaries

This guard prevents the later copy passes from running with a null starting node.

2

Create Copies of All Nodes and Map Originals to Copies

To create a new node for each original node and store the mapping from original to copy for later pointer assignments.

3

Assign 'next' and 'random' Pointers to Copied Nodes Using the Map

To correctly set the 'next' and 'random' pointers of each copied node by referencing the hash map.

4

Return the Head of the Deep-Copied List

To return the copied node corresponding to the original list's head as the entry point to the new list.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 13 Critical

old_to_copy = { None: None }

Initialize a hash map with None mapped to None.

Mapping None to None simplifies pointer assignments later by ensuring that when a node's next or random pointer is None, the copied pointer is also None without special checks.

Line 18 Critical

old_to_copy[curr] = copy

Map the original node to its copy in the hash map.

Storing this mapping enables O(1) lookup of the copied node for any original node, which is essential for correctly assigning 'next' and 'random' pointers later.

Line 24 Critical

copy.next = old_to_copy[curr.next]

Assign the 'next' pointer of the copied node.

Using the map to find the copy of the original node's 'next' ensures the copied list replicates the original's 'next' structure exactly.

Full line-by-line criticality + rationale for all 15 lines available on Pro.

Test Your Understanding

Why is a hash map necessary to correctly assign the 'random' pointers in the copied list?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Copy List with Random Pointer from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Copy List with Random Pointer drill

or drill a free problem

1	`# Definition for a Node.`
2	`# class Node:`
3	`# def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):`
4	`# self.val = int(x)`
5	`# self.next = next`
6	`# self.random = random`
7
8	`class Solution:`
9	`def copyRandomList(self, head: 'Node') -> 'Node':`
10	`if not head:`
11	`return None`
12
13	`old_to_copy = { None: None }`
14
15	`curr = head`
16	`while curr:`
17	`copy = Node(curr.val)`
18	`old_to_copy[curr] = copy`
19	`curr = curr.next`
20
21	`curr = head`
22	`while curr:`
23	`copy = old_to_copy[curr]`
24	`copy.next = old_to_copy[curr.next]`
25	`copy.random = old_to_copy[curr.random]`
26	`curr = curr.next`
27
28	`return old_to_copy[head]`