Clone Graph

Free with account Updated Nov 19, 2026 · 5 min read
On this page

    Problem statement

    Given a reference to one node of a connected undirected graph, return a deep copy of the whole graph. Each node has a value and a list of neighbours. The copy must use only new nodes, with the same values and the same connections.

    It looks like a simple traversal, but cycles make a naive recursive copy loop forever. The fix, a map from each original node to its copy, is the same trick used for Copy List with Random Pointer. Original problem: LeetCode 133.

    Example

    A four-node cycle 1–2–3–4 is copied into a separate graph with the same shape and values but entirely new nodes.
    A four-node cycle 1–2–3–4 is copied into a separate graph with the same shape and values but entirely new nodes.
    Input:  adjacency = [[2,4], [1,3], [2,4], [1,3]]   # node 1's neighbours are 2 and 4, …
    Output: the same adjacency, built from new nodes
    Input:  null
    Output: null

    Constraints (assumed)

    • 0 ≤ nodes ≤ 100; values are unique, from 1 to n.
    • The graph is connected and undirected; no self-loops or repeated edges.

    What this question tests

    • Graph traversal with a visited structure on a graph with cycles.
    • Using a hash map from old object to new object to rebuild references.
    • Clear reasoning about deep vs shallow copies.

    Questions to ask first

    1. Is the graph connected? (Here: yes, so one start node reaches everything.)
    2. Are values unique? If yes you could key by value; keying by node works either way.
    3. Directed or undirected? (Undirected; each edge appears in both neighbour lists.)
    4. Can the input be empty? (Yes, return null.)