Clone Graph

Clone Graph

Given a reference to a node in a connected undirected graph, return a deep copy (clone) of the graph.

Each node in the graph contains a value (val) and a list of its neighbors (neighbors).

class GraphNode {
    val: number
    neighbors: GraphNode[]
}

Graph Representation

The graph is represented as an adjacency list. For simplicity, each node's value is the same as its 1-indexed position. For example, the first node has val == 1, the second has val == 2, and so on.

The input is given as an adjacency list where adjList[i] contains the neighbor values for node i+1.

Return the cloned graph as an adjacency list in the same format.

Examples

Example 1:

Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: The graph has 4 nodes.
Node 1 connects to nodes 2 and 4.
Node 2 connects to nodes 1 and 3.
Node 3 connects to nodes 2 and 4.
Node 4 connects to nodes 1 and 3.
The cloned graph has the same structure.

Example 2:

Input: adjList = [[]]
Output: [[]]
Explanation: A single node with no neighbors.

Example 3:

Input: adjList = []
Output: []
Explanation: Empty graph (no nodes).

Constraints

• The number of nodes in the graph is in the range [0, 100].
• 1 <= Node.val <= 100
• Node.val is unique for each node.
• There are no repeated edges and no self-loops.
• The graph is connected and all nodes can be visited starting from the given node.

Expected Complexity

• Time: O(V + E) where V is the number of vertices and E is the number of edges
• Space: O(V) for the hash map and recursion stack