138. Copy List with Random Pointer - Detailed Explanation
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 isnull, 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. Therandompointer 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 isnull, the random pointer of the second node points to index 0 (the first node), and the random pointer of the third node isnull. 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 arenull. 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(wherenis the number of nodes in the list).- Node values are often integers (e.g.,
-10000 <= Node.val <= 10000or as given in problem, sometimes1 <= 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
randompointers 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
nextandrandomas 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
nextandrandompointers:- The clone’s
nextshould point to the clone of the original node’snextneighbor. - The clone’s
randomshould point to the clone of the original node’srandomtarget. By using the map, we find the correct clone nodes to assign. (If an original node’srandomwasnull, we leave the clone’s random asnull.)
- The clone’s
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 -> CB.random -> (null)C.random -> B
During the first pass, we create clonesA',B',C'with the same values asA, B, Crespectively, and store mappings{A: A', B: B', C: C'}. At this point,A'.next = B'.next = C'.next = NoneandA'.random = B'.random = C'.random = None. In the second pass, when at original nodeA, we setA'.next = B'(clone ofA.next) andA'.random = C'(clone ofA.random). ForB, we setB'.next = C'andB'.random = None(sinceB.randomis null). ForC, we setC'.next = NoneandC'.random = B'. Now the clone listA' -> B' -> C'is fully built with the correctnextsequence and random links.
Python Implementation:
Java Implementation:
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 likeA -> A' -> B -> B' -> C -> C'. Each original node’snextnow points to its clone, and each clone’snextpoints to the next original node. (At this point, clone nodes’ random pointers are not yet set; they default tonull.) -
Assign random pointers to the clones: Now use the interwoven structure to set the
randompointer of each clone. For each original nodeX, its cloneX'is right next to it. The original’s random pointerX.randompoints to some nodeY(or null). The clone’s random should point toY'(the clone ofY). Because of the interleaving,Y'isY.next(since we inserted clones after originals). So we can setX'.random = X.random.nextfor each original nodeX(ifX.randomis 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
nextpointers to skip over their clones (restoring the original list), and we fix the clonenextpointers 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:
Java Implementation:
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. Here1'is the clone of1,2'is the clone of2, and so on. Each original node is followed by its clone. At this stage, clone nodes have theirrandompointers default tonull. (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, ifX.random = Y(points to some nodeY), we assignX'.random = Y'. Thanks to the interleaving,Y'is exactlyY.next. In our example, original node 1’s random pointed to 3, so now clone1'gets its random pointer set to3'(since3’s clone is right after it). Original 4’s random pointed to 2, so clone4'getsrandom = 2'. Nodes 2 and 3 had no random, so their clones2'and3'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
nextpointers of original nodes to skip over the clones. Simultaneously, we fix thenextpointers of the clone nodes to point to each other. After detaching, the original list is back to1 → 2 → 3 → 4, and we have a separate cloned list:1' → 2' → 3' → 4' → null. Importantly, clone nodes1',2',3',4'have theirrandompointers set to3', null, null, 2'respectively (the same structure that original nodes1,2,3,4had, 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
randompointer to an original node instead of the clone of that original. Always ensure you’re linking clone to clone (never clone to original) for bothnextandrandom. Using a hash map or the interweaving trick helps avoid this by construction. -
Forgetting to handle
null: When using a map, remember to mapNone/nulltoNone(in Python) or check fornullbefore accessing pointers (in Java). If you don’t, you might run into aNoneTypeerror orNullPointerExceptionwhen 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
nextpointers 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
headisnull, simply returnnull. 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
nullor 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.)
Alternative Variations and Related Problems
- 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.
GET YOUR FREE
Coding Questions Catalog
