Clone graph

Hash Table Depth-First Search Breadth-First Search Graph Theory

64.7% acceptance

Jan 13, 2026

10532

4180

Given a reference of a node in a connected undirected graph. Return a deep copy (clone) of the graph. Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.

Solution

C++

Time O(1)

Space O(n)

LeetCode

solution.cpp

class Solution {
  unordered_map<Node*, Node*> visited;
public:
  Node* cloneGraph(Node* node) {
    if (!node) return nullptr;
    if (visited.count(node)) return visited[node];
    Node* clone = new Node(node->val);
    visited[node] = clone;
    for (Node* neighbor : node->neighbors)
      clone->neighbors.push_back(cloneGraph(neighbor));
    return clone;
  }
};