Introduction to Clone Pattern

The clone pattern builds an independent copy of a linked data structure by walking the original once while maintaining a mapping from each original node to its newly-created twin, so that any cross-reference in the original (a next pointer, a random pointer, a graph neighbor) can be re-wired to point into the new structure instead of the old one — the copy is a deep copy only if every reference inside it is also redirected, not just the values.

Recognize the pattern

• Problem says "deep copy", "clone", or "duplicate" a linked list, tree, or graph.
• Nodes carry more than one outgoing reference — e.g. next and random (Copy List with Random Pointer), or an arbitrary adjacency list (Clone Graph).
• The structure may contain cycles or forward references to nodes not yet created — a naive single pass would dereference a node before its clone exists.
• Modifying the copy must never be observable in the original (aliasing is explicitly forbidden).

Brute force → optimal

Brute force (plain linked list, no extra pointers): the iterative/recursive walk in the source text — create newNode per original node, chain via next. This works only when the sole reference is next; it has nothing to fall back on for a random pointer that may target a node further ahead that doesn't exist yet, or a cycle that would recurse forever.

Optimal (general clone pattern): use a HashMap<OldNode, NewNode>. Pass 1 creates every clone node and records old → new. Pass 2 re-walks the original and sets each clone's extra references by looking up map.get(old.next) / map.get(old.random) — the map guarantees the target clone already exists regardless of traversal order, so cycles and forward references are handled for free.

Complexity, derived

Let n = number of nodes, and for a graph let e = number of edges.

Linked list w/ random pointer: Pass 1 visits each node once → n node creations + n map insertions (O(1) amortized each) = O(n). Pass 2 visits each node once, doing 2 O(1) map lookups (next, random) = O(n). Total time O(n). Space: the map holds n entries → O(n) extra space (plus O(n) for the output copy itself, which is required, not "extra").

Graph (DFS/BFS clone): each of the n nodes is dequeued/visited once, and each of the e edges is inspected once to wire a neighbor → O(n + e) time, O(n) map + O(n) recursion/queue stack = O(n) space.

Naive recursive clone without a visited map on a cyclic graph never terminates — the recurrence T(n) = T(neighbor) + … revisits the same node, so there is no base case reached; this is why the map isn't an optimization here, it's a correctness requirement.

Traced example — copy list with random pointer

Original: A(val=1) → B(val=2) → C(val=3) → null, with A.random = C, B.random = B, C.random = A.

Result: A'→B'→C'→null, with A'.random=C', B'.random=B', C'.random=A' — every reference points inside the clone, none back into the original.

Java — clone a list with next and random pointers

class Node {
    int val; Node next, random;
    Node(int v) { val = v; }
}

public Node cloneList(Node head) {
    if (head == null) return null;
    Map<Node, Node> map = new HashMap<>();

    // Pass 1: create all clones
    for (Node cur = head; cur != null; cur = cur.next) {
        map.put(cur, new Node(cur.val));
    }
    // Pass 2: wire next and random using the map
    for (Node cur = head; cur != null; cur = cur.next) {
        map.get(cur).next   = map.get(cur.next);
        map.get(cur).random = map.get(cur.random);
    }
    return map.get(head);
}

Pitfalls

• Wiring random/extra references in the same pass as creation — the target clone may not exist yet, producing null links for forward references.
• Using ==/identity confusion: forgetting that map.get(null) correctly returns null, so no special-casing is needed for a null next or random.
• Shallow copy: copying a reference field (e.g. an embedded object) instead of cloning it recursively — later mutation of the "clone" leaks into the original through that shared reference.
• On graphs, omitting the visited/map check before recursing — cycles cause infinite recursion / stack overflow.

When to use / when not — trade-offs

Use the map-based clone whenever nodes carry more than a single forward-only reference, or the structure can contain cycles/shared subgraphs (linked list with random pointer, graph clone, DAG clone). Skip the map and use the plain iterative walk from a single next pointer when the structure is a simple singly-linked chain — the map adds O(n) space and hashing overhead with no correctness benefit there.

Alternative — serialize & deserialize: convert the structure to a flat representation (e.g. BFS order string) and rebuild it fresh. This avoids an explicit map but costs an extra full serialization pass and is harder to get right for arbitrary reference patterns; it shines when you also need persistence/transport (saving to disk, sending over network), which the map approach doesn't give you.

Takeaways

• The clone pattern's core trick is a node-identity map that decouples "create the copy" from "wire the copy's references", handling forward references and cycles safely.
• Two passes (create, then link) is the standard shape; one-pass variants exist (e.g. interleaving copies into the original list) but trade clarity for saving the map's space.
• A plain next-only clone is O(n) time/space and needs no map — reserve the map for multi-reference or cyclic structures.

Recall: Why does cloning a linked list with a random pointer in a single forward pass risk leaving some random fields null, and how does the two-pass hashmap approach fix it?

Adapted and extended from the course's Clone Pattern module (linked-list cloning) with the generalized hashmap technique for structures with non-linear references (random pointers, graphs), a standard technique covered in CLRS-adjacent interview literature.