138. Copy List with Random Pointer - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

We are given a singly linked list where each node has an additional random pointer that can point to any node in the list or to null. The task is to construct a deep copy of this list – i.e., create a new linked list of all new nodes such that each new node has the same value as the original node, the same next structure, and the same random pointer connections, but none of the new nodes should reference the original list. In other words, the copied list should “look” identical to the original list in terms of values and pointers, but it must consist entirely of new nodes.

The input is typically given as a list of pairs representing the nodes. Each node is described as [val, random_index], where val is the node’s value and random_index is the index (0-indexed) of the node in the list that the random pointer refers to (or null if the random pointer is null). The output should be the head of the new copied linked list, usually represented in the same format.

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]]
Explanation: The original list has 5 nodes with values 7 → 13 → 11 → 10 → 1. The random pointer of node with value 7 is null, the random pointer of node 13 points to the node at index 0 (the node with value 7), the random pointer of node 11 points to index 4 (node with value 1), the random pointer of node 10 points to index 2 (node with value 11), and the random pointer of node 1 points to index 0 (node 7). The output shows the new list has the same structure. (Each pair in the output corresponds to a new node with the same value and equivalent random pointer target as the input.) Essentially, we've created an entirely separate copy of the list with all pointers mirrored.

Example 2:

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]
Explanation: The original list has 2 nodes: values 1 → 2. The random pointer of the node at index 0 (value 1) points to index 1 (the node with value 2). The node at index 1 (value 2) has its random pointer pointing to index 1 as well (itself). The deep-copied list has two new nodes with the same values 1 and 2, and the same random pointer structure (node 1’s copy points to node 2’s copy, and node 2’s copy’s random points to itself).

Example 3:

Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]
Explanation: The original list has 3 nodes, all with value 3: 3 → 3 → 3. The random pointer of the first node is null, the random pointer of the second node points to index 0 (the first node), and the random pointer of the third node is null. The copied list contains three new nodes (also valued 3) with the same linking: the second new node’s random pointer points to the first new node, and others are null. Note that having duplicate values in nodes does not affect the deep copy process – we rely on node references, not values, to set random pointers.

Constraints:

0 <= n <= 10000 (where n is the number of nodes in the list).
Node values are often integers (e.g., -10000 <= Node.val <= 10000 or as given in problem, sometimes 1 <= Node.val <= 1000).
Random pointers can point to any node within the list (including the node itself) or be null.
The solution should ideally handle the list in one pass or linear time. Extra space usage should be considered (there are solutions that use extra memory and an optimal solution that uses constant extra space).
We must return the head of the copied linked list (with no connections to the original list).

The problem expects a deep copy of the linked list, meaning the original and copied lists are completely independent. Any changes to the new list should not affect the original list and vice versa.

Hints

Use a Map (Hash Table): Think about storing a mapping from each original node to its clone. This can help easily assign random pointers for cloned nodes by looking up where an original node’s random pointed, without confusion.
In-place Pointer Trick: There is an approach that doesn’t use extra maps. Consider inserting the cloned nodes directly into the original list (interleaving them with original nodes). How might this help in setting the random pointers and then extracting the new list?

Approaches

1. HashMap-Based Approach (Using Extra Space)

Idea: Use a hash map (or dictionary) to keep a mapping from each original node to its newly created clone node. This is a straightforward two-pass solution:

First pass: Traverse the original list and create a new clone node for each original node. Store the mapping from original -> clone in a hash map. During this pass, we only set the clone node’s value (and we can initialize next and random as null for now). The clones are not yet linked together; we just have them stored individually in the map.
Second pass: Traverse the original list again. For each original node, use the map to set its clone’s next and random pointers:
- The clone’s next should point to the clone of the original node’s next neighbor.
- The clone’s random should point to the clone of the original node’s random target. By using the map, we find the correct clone nodes to assign. (If an original node’s random was null, we leave the clone’s random as null.)

After these two passes, the map will have a clone for every original node, with all next and random pointers correctly established among the clones. We then return the clone corresponding to the original head as the new head.

Walkthrough Example (Approach 1):
Imagine a simple list A -> B -> C where:

A.random -> C
B.random -> (null)
C.random -> B
During the first pass, we create clones A', B', C' with the same values as A, B, C respectively, and store mappings {A: A', B: B', C: C'}. At this point, A'.next = B'.next = C'.next = None and A'.random = B'.random = C'.random = None. In the second pass, when at original node A, we set A'.next = B' (clone of A.next) and A'.random = C' (clone of A.random). For B, we set B'.next = C' and B'.random = None (since B.random is null). For C, we set C'.next = None and C'.random = B'. Now the clone list A' -> B' -> C' is fully built with the correct next sequence and random links.

Python Implementation:

Python3

. . . .

Java Implementation:

Java

. . . .

Complexity Analysis: This approach visits each node twice, so the time complexity is O(n) for n nodes. The space complexity is O(n) as well, because of the hash map that stores n key-value pairs (and of course, the output list of n new nodes, which doesn’t count as extra auxiliary space but is required output). This method is easy to implement and understand. The trade-off is the extra memory used for the map.

2. Optimal Approach (Pointer Manipulation Without Extra Space)

Idea: This approach avoids using additional O(n) space by temporarily modifying the linked list structure to facilitate the copy. The algorithm works in three steps:

Interweave original and cloned nodes: Traverse the original list, and insert each clone node right after its original node. For example, if the original list is A -> B -> C, after this step it will look like A -> A' -> B -> B' -> C -> C'. Each original node’s next now points to its clone, and each clone’s next points to the next original node. (At this point, clone nodes’ random pointers are not yet set; they default to null.)
Assign random pointers to the clones: Now use the interwoven structure to set the random pointer of each clone. For each original node X, its clone X' is right next to it. The original’s random pointer X.random points to some node Y (or null). The clone’s random should point to Y' (the clone of Y). Because of the interleaving, Y' is Y.next (since we inserted clones after originals). So we can set X'.random = X.random.next for each original node X (if X.random is not null). This assigns the correct random targets to every clone.
Detach the cloned list from the original: Finally, restore the original list and extract the clones. We traverse the interwoven list and separate it into two lists. We fix the original node next pointers to skip over their clones (restoring the original list), and we fix the clone next pointers to point to each other (forming the new cloned list). After this, the original list is back to normal, and we obtain the head of the cloned list as our result.

This way, we achieve the deep copy without using a separate hash map. All we used was a few pointer reassignments.

Python Implementation:

Python3

. . . .

Java Implementation:

Java

. . . .

Complexity Analysis: We perform a constant number of passes over the list (three passes), so the time complexity is O(n). The space complexity is O(1) additional space (we only use a few temporary pointers). We do create n new nodes, but that’s required for the output anyway. This approach is optimal in space since it avoids the extra O(n) hash map. The trade-off is that it mutates the list temporarily, which is a bit trickier to implement and reason about, but ultimately restores the list to its original form.

Step-by-Step Walkthrough (Optimal Approach)

Visual illustration of a linked list with next and random pointers. In this example, we have a list of four nodes 1 → 2 → 3 → 4 → null. Straight arrows denote the next pointers (forming the sequence 1-2-3-4). The curved arrows show random pointers: here, node 1’s random pointer goes to node 3, and node 4’s random pointer goes to node 2 (nodes 2 and 3 have their random pointers set to null). We will use this list to demonstrate the copying process step by step.

Step 1: Insert cloned nodes after originals. We create a copy of each node and insert it immediately after the original node. After this interweaving, the list looks like: 1 → 1' → 2 → 2' → 3 → 3' → 4 → 4' → null. Here 1' is the clone of 1, 2' is the clone of 2, and so on. Each original node is followed by its clone. At this stage, clone nodes have their random pointers default to null. (The original nodes still retain their original random pointers for now.)
Step 2: Assign random pointers to cloned nodes. Now we set the random pointer of each clone. For each original node X, if X.random = Y (points to some node Y), we assign X'.random = Y'. Thanks to the interleaving, Y' is exactly Y.next. In our example, original node 1’s random pointed to 3, so now clone 1' gets its random pointer set to 3' (since 3’s clone is right after it). Original 4’s random pointed to 2, so clone 4' gets random = 2'. Nodes 2 and 3 had no random, so their clones 2' and 3' remain with no random as well. After this step, every clone’s random pointer mirrors its original’s random (but pointing to clone targets).
Step 3: Detach the new list from the original. Finally, we separate the combined list into two individual lists. We restore the original list by fixing the next pointers of original nodes to skip over the clones. Simultaneously, we fix the next pointers of the clone nodes to point to each other. After detaching, the original list is back to 1 → 2 → 3 → 4, and we have a separate cloned list: 1' → 2' → 3' → 4' → null. Importantly, clone nodes 1',2',3',4' have their random pointers set to 3', null, null, 2' respectively (the same structure that original nodes 1,2,3,4 had, but all pointing within the cloned list). We return the head of this cloned list as the result.

By following these steps, we achieved a deep copy without using extra storage for a map. The original list remains unmodified at the end (which is often important if this were part of a bigger program), and we have the new list correctly duplicated.

Common Mistakes

Mixing up original and clone pointers: A frequent mistake is assigning a cloned node’s random pointer to an original node instead of the clone of that original. Always ensure you’re linking clone to clone (never clone to original) for both next and random. Using a hash map or the interweaving trick helps avoid this by construction.
Forgetting to handle null: When using a map, remember to map None/null to None (in Python) or check for null before accessing pointers (in Java). If you don’t, you might run into a NoneType error or NullPointerException when a node’s random pointer is null.
Not restoring the original list (in Approach 2): After interweaving nodes, you must separate the two lists. A common bug is to accidentally break the original list or the copied list links. Carefully reassign the next pointers in the third step of the optimal approach. Forgetting to restore them can mutate the original list unexpectedly.
Off-by-one errors in traversal: When separating the lists in approach 2, be mindful of when to move your pointers. It’s easy to lose track of nodes if you advance incorrectly. Always move the pointers in lock-step for original and clone during separation (as shown in the implementations).

Edge Cases

Empty list: If head is null, simply return null. There’s nothing to copy.
Single node: A list with one node should return a new single node. Make sure the random pointer (which could be null or pointing to itself) is handled correctly.
All random pointers null: If none of the nodes have a random pointer (all are null), the problem reduces to just cloning a normal singly linked list. Your solution should still handle this and produce a correct copy.
Random pointer to self: A node’s random pointer may point to itself. Ensure that in the copied list, the clone’s random also points to itself (a new self-reference).
Multiple nodes pointing to one node: It’s possible multiple random pointers in the list reference the same target node. The clone list should reflect the same scenario (multiple clones’ randoms pointing to the same target clone).
Random pointers forming a cycle: Random pointers can create cycles or complex graphs (e.g., node A’s random -> node B, and node B’s random -> node A). The deep copy should not get stuck or create new unintended cycles; it must replicate the exact structure of random relations in the new list. (Approach 1 with a map or approach 2 both naturally handle this as long as you follow the procedure.)

Clone Graph (LeetCode 133): This is a very similar problem where each node in a graph has pointers to neighbors. The task is to deep-copy the entire graph. The concept of using a hash map to track visited nodes (or an interleaving trick in a graph traversal) is analogous to the random list copy problem.
Clone Binary Tree with Random Pointer (LeetCode 1485): In this variation, a binary tree node has an extra random pointer to any other node. The deep copy solution for that problem is conceptually similar: you can use a hash map or recursive DFS with memoization to clone nodes, or even adapt the interweaving approach to tree structure.
Flatten a Multilevel Doubly Linked List (LeetCode 430): While not about random pointers, this problem involves copying/flattening pointers from child lists into a single list. It tests understanding of manipulating node pointers in a complex linked structure, similar in spirit to dealing with random pointers.

138. Copy List with Random Pointer - Detailed Explanation

Problem Statement

Hints

Approaches

1. HashMap-Based Approach (Using Extra Space)

2. Optimal Approach (Pointer Manipulation Without Extra Space)

Step-by-Step Walkthrough (Optimal Approach)

Common Mistakes

Edge Cases

Alternative Variations and Related Problems