Copy Random Pointer LeetCode 138 Guide

LeetCode 138, Copy List with Random Pointer, presents a linked list where each node has two pointers: next, which points to the next node in sequence, and random, which can point to any node in the list or to null. Your task is to construct a complete deep copy — a brand-new linked list with brand-new nodes — and return its head. No original node may appear in the copied list.

The challenge is the random pointer. Copying next pointers is straightforward, but random can point to any node, including one that has not been created yet at the time you are processing the current node. This forward-reference problem rules out a single naive pass and demands a strategy to handle pointers to not-yet-created nodes.

Key constraints for quick reference: there are 0 to 1000 nodes, node values are in -10000..10000, and random is either null or points to some node in the original list. The returned list must be a true deep copy — no shared node references between original and clone.

The hashmap approach solves the forward-reference problem by separating node creation from pointer assignment. In the first pass, iterate through the original list and create a clone for every node, storing the mapping original → clone in a hash map. At this point, do not set any pointers — just allocate nodes and record the mapping.

In the second pass, iterate again. For each original node, look up its clone in the map and set clone.next = map[original.next] and clone.random = map[original.random], handling null by mapping null to null directly. Because all clones exist after the first pass, the second pass can resolve every pointer in O(1) per node.

Total time complexity is O(n) and space complexity is O(n) for the hashmap. This is the cleanest approach for interview settings — easy to explain, easy to implement correctly, and trivial to extend to graphs (it is essentially the same algorithm as Clone Graph).

The interleave approach achieves O(1) extra space by using the list structure itself as an implicit mapping. Instead of a hashmap, it physically places each clone node immediately after its original: A→A'→B→B'→C→C'. The clone is always at original.next, so the mapping is encoded in the list layout itself.

Setting random pointers is then elegant: clone.random = original.random.next. Because every original's clone is its immediate successor, original.random.next is exactly the clone of the random target. This works for all nodes simultaneously because the layout guarantees the invariant throughout the pass.

The final step separates the interleaved list back into two independent lists: restore original.next = original.next.next (skipping the clone) and set clone.next = clone.next.next (skipping the original). This split must be done carefully to avoid corrupting either list during traversal.

The interleave trick exploits a simple invariant: after step 1, every clone is exactly one hop after its original. So given any original node X, its clone is X.next. This means that to find the clone of X.random, you do not need a hashmap — you just follow X.random.next.

This invariant holds across all nodes simultaneously. Whether X.random points forward, backward, or to itself, X.random.next is always its clone because every node in the list had a clone inserted right after it in step 1. No extra data structure is needed beyond the modified list itself.

The separation step in step 3 requires care. If you naively iterate and set original.next = original.next.next, you must save clone.next before overwriting original.next, otherwise you lose your traversal pointer. A clean implementation processes the split in a single pass, restoring both lists node by node without any intermediate storage.

The recursive approach mirrors the graph clone pattern. Define a helper copyNode(node) that returns the clone of the given node, creating it if it does not already exist. The memo dictionary maps original nodes to their clones and serves the same role as the hashmap in the iterative approach.

The base cases are: if node is null, return null; if node is already in memo, return memo[node]. Otherwise, create a new node, store it in memo immediately (before recursing), then set clone.next = copyNode(node.next) and clone.random = copyNode(node.random). Storing the clone before recursing prevents infinite loops when random pointers form cycles.

Complexity is O(n) time and O(n) space — identical to the iterative hashmap approach but expressed recursively. For very long lists (n = 1000), Python's default recursion limit may be reached; an iterative hashmap is safer in production. However, the recursive version is the most natural formulation and very easy to derive on a whiteboard.

Python hashmap version: iterate once to build the map, iterate again to wire next and random. About 10 lines. Interleave version: three loops — insert clones, set random, separate lists. About 15 lines but O(1) space. Both are clean and interview-ready. The hashmap version is easier to explain under time pressure; the interleave version impresses if asked for the O(1) space follow-up.

Java hashmap version: use a HashMap<Node, Node>. Same two-pass structure as Python. Java interleave version is line-for-line equivalent — the only language difference is explicit null checks and the Node constructor. Both run in O(n) time. The recursive version in Java requires the same memo map and a private helper method.

Interview strategy: lead with the hashmap approach, explain it clearly, and code it. If the interviewer asks for O(1) space, describe the interleave trick before coding. If they ask for a recursive solution, derive it from the hashmap version by replacing the iterative loop with a recursive call and noting that the memo serves the same purpose.

Copy List with Random Pointer belongs to the deep copy family alongside Clone Graph (LeetCode 133). Both use the same hashmap-of-originals-to-clones pattern; the only difference is that a graph node has a list of neighbors instead of just next and random. If you can solve one, you can solve the other with minor structural changes.

The interleave technique — encoding a mapping in the structure of the data itself — appears in other problems too. Reverse Nodes in k-Group (LeetCode 25) and Reorder List (LeetCode 143) both rely on careful multi-pointer manipulation of a list without auxiliary storage, requiring the same disciplined pointer bookkeeping.

For memoized recursion, the pattern generalizes to any graph traversal with potential cycles. Dynamic programming problems that require copying or reconstructing substructures share the "store result before recursing" discipline. Practicing the three approaches here — hashmap, interleave, recursive memo — covers a wide range of interview problems in the deep copy and linked list pattern family.