Copy List with Random Pointer: LeetCode 138 Walkthrough

LeetCode #138, Copy List with Random Pointer, is one of the most frequently asked linked list problems at top tech companies. It tests whether you can deep copy a data structure where nodes reference each other in non-trivial ways — a skill that comes up in real codebases whenever you need to duplicate complex object graphs.

The twist that makes this problem interesting is the random pointer. Every node has a next pointer like a standard linked list, but it also has a random pointer that can point to any node in the list — or to null. You cannot simply iterate and copy nodes one by one because a random pointer might reference a node you have not created yet.

In this walkthrough, you will learn two approaches for solving copy list random pointer leetcode style: a clean hash map solution and a clever O(1) space interleaving technique. Both are worth knowing for interviews, though one is far safer under pressure.

You are given a linked list where each node contains three fields: a value, a next pointer to the following node, and a random pointer to any arbitrary node in the list (or null). Your task is to construct a completely independent deep copy of this list. No node in your copy should reference any node in the original list.

This is different from a shallow copy where you just duplicate the head pointer. A deep copy linked list means creating entirely new nodes with the same values, then wiring up both next and random pointers to point to the corresponding new nodes — not the originals.

The core difficulty is the random pointer. When you are creating a clone of node A and its random pointer targets node D, you might not have created node D yet. This chicken-and-egg problem is what separates this from a basic linked list copy, and it is exactly the pattern interviewers want to see you handle.

The hash map approach is the cleanest way to solve copy list random pointer leetcode problems. The idea is straightforward: use a dictionary that maps each original node to its corresponding clone. With this mapping in hand, wiring up next and random pointers becomes trivial.

In the first pass, iterate through the original list and create a clone node for every original node. Store the mapping original -> clone in your hash map. Do not worry about pointers yet — just create the nodes with the correct values.

In the second pass, iterate through the original list again. For each original node, look up its clone in the map. Then set clone.next to the clone of original.next (looked up in the map), and set clone.random to the clone of original.random (also from the map). If next or random is null, the clone pointer stays null.

This leetcode 138 solution runs in O(n) time and O(n) space, where n is the number of nodes. The extra space comes from the hash map storing n entries. The logic is simple, hard to get wrong, and easy to explain to an interviewer.

The interleaving copy technique eliminates the hash map entirely by using the list structure itself as the mapping. The idea is to insert each clone node directly after its original, creating an interleaved list where originals and clones alternate. This gives you O(1) lookup: the clone of any node is simply node.next.

Step one: iterate through the original list and insert a clone after each original. For node A -> B -> C, you get A -> A' -> B -> B' -> C -> C'. Each clone has the same value as its original. The next pointers of the originals now point to their clones.

Step two: iterate through the interleaved list and set the random pointers for each clone. If original.random points to node D, then clone.random should point to D.next (which is D's clone). This is where the interleaving pays off — you do not need a map because the clone is always one step ahead of its original.

Step three: separate the two lists. Restore the original list's next pointers and extract the clone list. After separation, both lists should be independent and correctly wired. This interleaving copy technique achieves O(n) time and O(1) extra space, but the pointer manipulation is delicate.

In a standard singly linked list, deep copying is a one-pass operation. You create each clone node as you iterate, setting clone.next to the next clone you create. The forward-only structure means every dependency is resolved in order. Random pointers break this entirely.

A random pointer can reference any node in the list — including nodes you have not visited or created yet. Node 1's random pointer might point to node 7, but when you are cloning node 1, node 7's clone does not exist yet. You cannot set clone1.random without first creating clone7, but clone7 comes later in the iteration.

This is the same fundamental challenge you face in Clone Graph (#133), where a node can reference neighbors that have not been visited. The solution is the same in both cases: either build a complete mapping first (hash map) or find a way to co-locate clones with originals (interleaving). Recognizing this shared pattern between random pointer clone problems and graph cloning is exactly the kind of insight interviewers look for.

Interviewers expect you to handle edge cases without being prompted. The most important one is the empty list: if the head is null, return null immediately. Both approaches handle this naturally, but explicitly checking avoids null pointer errors in your first loop.

A single-node list is another common test. The node's random pointer might be null, or it might point to itself. If random points to self, your clone's random must point to the clone — not the original. The hash map approach handles this automatically since the clone is already in the map. The interleaving approach also works because clone = original.next and original.random.next is the clone.

Other edge cases include multiple nodes with random pointing to the same target, random pointers that are all null (effectively a normal linked list), and lists where every random pointer points to the head. None of these require special code if your approach is correct, but walk through them verbally to show thoroughness.

LeetCode #138 is ultimately about deep copying a data structure with arbitrary references. The same pattern appears in Clone Graph (#133), where you deep copy a graph with adjacency lists. If you can solve one, you can solve the other — they both require a mapping from original to clone and a systematic way to wire connections.

The hash map approach teaches you to separate construction from wiring. Build all clones first, then connect them. This two-phase pattern is useful far beyond linked lists: it applies to any scenario where objects reference each other and you need a complete copy.

The interleaving approach teaches you to think creatively about using existing structure to avoid extra space. It is a beautiful algorithmic trick, but in interviews, clarity and correctness matter more than space optimization. Choose the approach that lets you code confidently under time pressure.

Practice this pattern with YeetCode flashcards to build recall for deep copy problems. When you see "clone" or "deep copy" in a problem statement, your first thought should be hash map mapping — and the interleaving trick as an optimization if asked.