Generated by Codex with GPT-5

Quick facts

What the problem is really asking

Each node in the list has two outgoing pointers:

  • next, which gives the usual linked-list order
  • random, which can point to any node in the list or to None

The task is to build a deep copy, not just another pointer to the same nodes.

That means the copied list must preserve all of the original structure:

  • the copied nodes must appear in the same next order
  • every copied node’s random pointer must point to the copied version of the original target
  • no copied pointer is allowed to point back into the original list

So the real challenge is not cloning node values. The real challenge is preserving relationships between nodes when some of those relationships jump arbitrarily across the list.

The key insight

For every original node, the algorithm eventually needs a fast way to answer this question:

given an original node, where is its clone?

That is why the most natural first solution uses a hashmap from original node to copied node.

Once that mental model is clear, the space-optimized solution becomes much easier to see. Instead of storing the mapping in a separate dictionary, the algorithm stores it directly inside the list by temporarily placing each clone immediately after its original node.

If original.next is the clone, then original.random.next is the clone of the random target.

That turns random-pointer assignment into a simple pointer hop.

How to derive the best solutions

The cleanest first pass is the hashmap solution.

In that approach:

  1. make one clone for every original node
  2. store original -> clone in a dictionary
  3. make a second pass to wire clone.next and clone.random through the dictionary

That already gives a correct O(n) time solution, and it is often the easiest solution to explain under interview pressure.

The next question is whether the dictionary can be removed.

To do that, the algorithm needs another way to recover the clone for any original node in constant time. The trick is to interleave the lists:

  • original A is followed by clone A'
  • original B is followed by clone B'
  • original C is followed by clone C'

After that first pass, the list looks like this:

A -> A' -> B -> B' -> C -> C'

Now the mapping is implicit:

  • clone of A is A.next
  • clone of B is B.next
  • clone of the node pointed to by A.random is A.random.next

That leads to a three-pass solution:

  1. insert each clone right after its original
  2. assign each clone’s random pointer using original.random.next
  3. detach the interleaved structure into the original list and the copied list

This keeps the runtime linear and reduces auxiliary space to O(1) if the output nodes themselves are not counted.

Best approaches

  • Hashmap clone lookup: easiest to derive and easiest to explain. Time O(n), extra space O(n).
  • Interleaving clones with originals: same O(n) time, but only O(1) auxiliary space. This is the optimal answer for the standard LeetCode version.

Why the interleaving solution works

The reason the trick works is that the original-to-clone mapping stays available at every step.

After the first pass, every original node is immediately followed by its clone. So if the original node X has a random pointer to some node Y, then:

  • X.random is Y
  • Y.next is Y', the clone of Y

So the correct copied random pointer is simply:

X'.random = X.random.next

The final pass then separates the two intertwined lists carefully:

  • each original node skips over its clone to restore the old list
  • each clone skips over the next original node to point to the next clone

Because every pointer rewrite is local and each node is visited a constant number of times, the whole algorithm stays linear.

Python solution

from typing import Optional


# LeetCode provides the Node class.
# class Node:
#     def __init__(
#         self,
#         x: int,
#         next: 'Optional[Node]' = None,
#         random: 'Optional[Node]' = None,
#     ) -> None:
#         self.val = int(x)
#         self.next = next
#         self.random = random


class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if head is None:
            return None

        self._insert_clones_after_originals(head)
        self._assign_clone_random_pointers(head)
        return self._detach_cloned_list(head)

    def _insert_clones_after_originals(self, head: 'Node') -> None:
        current = head

        while current is not None:
            cloned_node = Node(current.val)
            cloned_node.next = current.next
            current.next = cloned_node
            current = cloned_node.next

    def _assign_clone_random_pointers(self, head: 'Node') -> None:
        current = head

        while current is not None:
            cloned_node = current.next

            # If the original points at some random target, the clone of that
            # target sits immediately after it in the interleaved list.
            if current.random is not None:
                cloned_node.random = current.random.next

            current = cloned_node.next

    def _detach_cloned_list(self, head: 'Node') -> 'Node':
        current = head
        cloned_head = head.next

        while current is not None:
            cloned_node = current.next
            next_original = cloned_node.next

            current.next = next_original
            cloned_node.next = (
                next_original.next if next_original is not None else None
            )

            current = next_original

        return cloned_head

Interview follow-ups

What if the interviewer wants the simplest correct solution first?

Start with the hashmap solution. In the first pass, create a clone for every original node and store original -> clone. In the second pass, set clone.next = map[original.next] and clone.random = map[original.random], handling None naturally. This works because the dictionary gives constant-time access to the clone of any original node, which is exactly the missing piece the problem needs. The tradeoff is space: it uses O(n) auxiliary memory, but it is often the clearest explanation and a good stepping stone to the optimal version.

What if modifying the original list, even temporarily, is not allowed?

Then the interleaving trick is off the table, because it relies on inserting clone nodes into the original list during the middle of the algorithm. In that version of the problem, the hashmap approach becomes the right answer. It still runs in O(n) time and is easy to reason about, but it pays O(n) extra space to preserve the mapping externally instead of encoding it in the list structure itself.

What if this were an arbitrary graph instead of a linked list with random pointers?

The same deep-copy idea still applies, but the interleaving trick no longer works because there is no single next chain that lets the algorithm place each clone beside its original in a controlled way. For a general graph, the standard answer is DFS or BFS plus a hashmap from original node to cloned node. The traversal ensures every reachable node is visited once, and the hashmap prevents duplicate cloning while making it possible to reconnect edges correctly. The complexity remains O(V + E) time and O(V) extra space, which is optimal for that more general setting.

What if the interviewer asks how to verify the copy is truly deep?

A good practical answer is to compare structure, not object identity. Traverse the original and copied lists in parallel and confirm that corresponding nodes have the same values and matching relative next and random relationships, while also confirming that no copied node is the same object as an original node. In tests, it is useful to mutate one list afterward and confirm the other does not change. That proves the algorithm copied the topology instead of merely sharing references. The tradeoff is that verification itself may need auxiliary bookkeeping in test code, even though the production cloning algorithm does not.

Practical takeaway

This problem becomes much easier once it is framed as a mapping problem:

  • every original node needs a unique clone
  • every pointer in the original structure must be redirected to the corresponding clone

The hashmap solution makes that mapping explicit. The optimal solution makes the same mapping implicit by storing each clone directly next to its original.

That is the reusable interview lesson: when a problem looks like “copy a structure with cross-links,” first ask how the algorithm will recover the copied version of an original node quickly. Once that mapping is clear, the rest of the solution usually falls into place.