Clone Graph

Medium~25 min

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 (val) and a list (neighbors) of its adjacent nodes.

class Node {
    val: int
    neighbors: Node[]
}

The graph is represented as an adjacency list where the index of the array represents the node value (1-indexed). For example, [[2,4],[1,3],[2,4],[1,3]] means:

  • Node 1 has neighbors [2, 4]
  • Node 2 has neighbors [1, 3]
  • Node 3 has neighbors [2, 4]
  • Node 4 has neighbors [1, 3]

Return the adjacency list of the cloned graph 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: There are 4 nodes. Node 1 connects to 2 and 4, node 2 connects to 1 and 3, etc. The deep copy has the same structure but all new node objects.
Example 2
Input: adjList = [[]]
Output: [[]]
Explanation: There is a single node with no neighbors.
Example 3
Input: adjList = []
Output: []
Explanation: The graph is empty (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 in the graph
  • The graph is connected and all nodes can be visited starting from the given node
  • Expected time complexity: O(V + E)
Code
Ctrl+EnterRun|Ctrl+⇧+EnterSubmit
Output

Run your code to see results

Use Cmd+Enter to run