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.
For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y.
Return the head of the copied linked list.
The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:
val: an integer representing Node.valrandom_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.Your code will only be given the head of the original linked list.
Example 1:
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]] Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]
Example 2:
Input: head = [[1,1],[2,1]] Output: [[1,1],[2,1]]
Example 3:
Input: head = [[3,null],[3,0],[3,null]] Output: [[3,null],[3,0],[3,null]]
Constraints:
0 <= n <= 1000-104 <= Node.val <= 104Node.random is null or is pointing to some node in the linked list.Problem Overview: You receive a linked list where each node contains a next pointer and an additional random pointer that can point to any node in the list or null. The goal is to create a deep copy of the entire structure so that both next and random relationships are preserved without referencing the original nodes.
Approach 1: Using Hash Map (O(n) time, O(n) space)
This method uses a hash table to map each original node to its cloned node. First iterate through the list and create a new node for every original node while storing the mapping original → copy. During a second pass, assign the next and random pointers for each cloned node using constant-time hash lookups. The key insight is that the mapping lets you instantly find the cloned version of any node referenced by random. This approach is easy to reason about and minimizes pointer manipulation, making it a reliable choice during interviews.
Approach 2: Interleaving Nodes (O(n) time, O(1) space)
This technique removes the need for extra memory by weaving copied nodes directly into the original list. For each original node, create its copy and insert it immediately after the original (for example: A → A' → B → B'). Because every copy sits next to its original, the random pointer of the copy can be assigned using original.random.next. After all random pointers are fixed, perform another traversal to detach the interleaved nodes and rebuild two separate lists. The trick works because adjacency gives constant-time access to the cloned counterpart of any node.
Hash Map Traversal Variant (O(n) time, O(n) space)
Some implementations combine node creation and pointer assignment into a single traversal. When visiting a node, create its copy if it does not exist in the map and ensure both next and random targets also exist in the map. This style reduces explicit passes over the list but still relies on the same linked list traversal and hash mapping idea. Complexity remains identical to the standard hash map approach.
Recommended for interviews: Start with the hash map solution because it clearly demonstrates how to manage node relationships and guarantees correctness with minimal pointer tricks. Once that is established, the interleaving method shows stronger mastery of pointer manipulation and space optimization. Interviewers often expect candidates to recognize the O(1) extra space trick, but presenting the hash map version first proves you understand the structure before optimizing it.
This approach involves using a hash map to build a one-to-one mapping from the original list nodes to the copied list nodes. The algorithm consists of the following main steps:
next chain of the deep copy, while storing the mapping of original nodes to copied nodes in a hash map.random pointers in the copied list by referring back to the original nodes' random pointers.The solution uses a two-pass algorithm:
next and random linkages.next and random pointers for the copied nodes. These are set using the previously built dictionary.Time Complexity: O(n), where n is the number of nodes in the linked list, because we pass through the list twice.
Space Complexity: O(n) due to the use of a dictionary that stores mappings for each node.
This approach involves interleaving the cloned nodes with original ones in the same list. The three main steps include:
The solution works in three main phases:
next pointer is redirected to its clone, and the clone points to the following original node.next pointers to point to the original list and cloned list separately.Time Complexity: O(n) as we traverse the list three times independently.
Space Complexity: O(1) as we only use a few additional pointers and no extra data structures.
This approach involves using a hash map to keep track of the relationship between the original nodes and their corresponding nodes in the copied list. First, traverse the original linked list to create a copy of each node, while storing the mapping from original nodes to copied nodes. In the second pass, assign the 'next' and 'random' pointers in the copied list based on this mapping.
The solution involves creating a deep copy of each node and storing the original-to-copy mappings in a hash map. After creating the copies, the 'next' and 'random' pointers for each copied node are assigned using the hash map. This ensures that the structure of the new list mirrors the original.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of nodes in the linked list. We traverse the list twice.
Space Complexity: O(n) due to the auxiliary space used by the hash map.
This approach involves interleaving the copied nodes with the original nodes in the list. By placing each copied node immediately after its original node, the 'random' pointers can be easily assigned by looking at the 'random' pointers of the original nodes. Finally, the original and copied nodes are separated to complete the process.
This C code combines node copying with in-place operations to handle the node connections. The copied nodes are interwoven with original nodes, which makes setting 'random' pointers straightforward since each copied node follows its original. After setting all pointers, it separates the intertwined nodes to complete the deep copy separation.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), as we traverse the list a few times but each operation is linear.
Space Complexity: O(1), since no additional data structures are used apart from constant space variables.
| Approach | Complexity |
|---|---|
| Approach 1: Using Hash Map | Time Complexity: O(n), where n is the number of nodes in the linked list, because we pass through the list twice. Space Complexity: O(n) due to the use of a dictionary that stores mappings for each node. |
| Approach 2: Interleaving Nodes | Time Complexity: O(n) as we traverse the list three times independently. Space Complexity: O(1) as we only use a few additional pointers and no extra data structures. |
| Hash Map Traversal | Time Complexity: O(n), where |
| Interleaving Method | Time Complexity: O(n), as we traverse the list a few times but each operation is linear. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Map Mapping | O(n) | O(n) | Best for clarity and quick implementation during interviews |
| Hash Map Single Traversal Variant | O(n) | O(n) | When combining node creation and pointer setup in one pass |
| Interleaving Nodes Method | O(n) | O(1) | When memory usage matters or to demonstrate pointer manipulation skills |
Copy List with Random Pointer - Linked List - Leetcode 138 • NeetCode • 159,494 views views
Watch 9 more video solutions →Practice Copy List with Random Pointer with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor