What is the time and space complexity of Copy List with Random Pointer?

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

Copy List with Random Pointer

Med

Concept

Code

Loading editor...

Tap Analyze to see visualization

Click Analyze to visualize

See step-by-step execution, variables, and output

Variables

Run code to see variables

Output

Console output will appear here

Press Space to start•← → to step•? all shortcuts

Solution Guide: Copy List with Random Pointer

Approach

Two-pass approach using a hash map. First pass: iterate through the original list and create a clone of each node, storing the mapping in a plain object keyed by node ID. Second pass: iterate again to set next and random pointers on each clone using the map.

Complexity Analysis

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

Pattern

Linked List (Hash Map Clone)

Why It Works

The map provides O(1) lookup from any original node to its clone. The first pass ensures every clone exists before the second pass wires up next and random pointers, which may point to any node in the list.

Updated Feb 2026