Practice/LinkedIn/Leetcode 133. Clone Graph

Leetcode 133. Clone Graph

CodingMust

Problem

You are given a reference to a node in a connected undirected graph. Your task is to create and return a deep copy of the entire graph.

Each node in the graph contains an integer value and a list of its neighboring nodes. The graph is represented using an adjacency list where each node holds references to all nodes directly connected to it.

Your cloned graph must be completely independent of the original — modifying the clone should not affect the original graph in any way. Every node in the original graph must map to exactly one unique node in the cloned graph, preserving all structural relationships including cycles and shared neighbors.

Requirements

1. Create a complete deep copy of all nodes reachable from the given node
2. Preserve all edge relationships — if node A is connected to node B in the original, their clones must also be connected
3. Handle cycles correctly — if the graph contains cycles, ensure the cloned graph maintains the same cycle structure
4. Each original node must correspond to exactly one cloned node (no duplicates)
5. Return the cloned version of the input node
6. If the input is null/None, return null/None

Constraints

• Number of nodes in the graph: 0 ≤ n ≤ 100
• Node values are unique and range from 1 to 100
• The graph is undirected (if A connects to B, then B connects to A)
• The graph is connected (all nodes are reachable from the given node)
• No self-loops or multiple edges between the same pair of nodes
• Expected time complexity: O(n + e) where n is nodes and e is edges
• Expected space complexity: O(n) for storing the cloned graph

Examples

Example 1:

Input: Node 1 with no neighbors Output: A new Node with value 1 and empty neighbors list Explanation: A single isolated node is cloned with the same value and no connections.

Example 2:

Input: Node 1 connected to Node 2 (bidirectional) Adjacency list: \{\{1, [2]\}, \{2, [1]\}\} Output: Cloned Node 1 connected to cloned Node 2 Explanation: The two nodes and their mutual connection are preserved in the clone.

Example 3:

Input: Four nodes in a square formation Node 1 connects to [2, 4] Node 2 connects to [1, 3] Node 3 connects to [2, 4] Node 4 connects to [1, 3] Output: A cloned graph maintaining the same square structure Explanation: All four nodes and their connections form an identical but independent copy.

Example 4:

Input: null Output: null Explanation: An empty graph input should return null.