Clone Graph

shriyanshi24jindal

Mar 29th, 2026

138

Never

Not a member of GistPad yet? Sign Up, it unlocks many cool features!

Java 6.20 KB | None | 0 0

copy raw download clone embed print report

/*
Definition for a Node.
class Node {
public int val;
public List<Node> neighbors;
public Node() {
val = 0;
neighbors = new ArrayList<Node>();
}
public Node(int _val) {
val = _val;
neighbors = new ArrayList<Node>();
}
public Node(int _val, ArrayList<Node> _neighbors) {
val = _val;
neighbors = _neighbors;
}
}
*/
class Solution {
public Node cloneGraph(Node node) {
// Create a map to store original nodes -> cloned nodes.
Map<Node, Node> clonedMap = new HashMap<>();
return dfs(node, clonedMap);
}
public Node dfs(Node node, Map<Node, Node> clonedMap)
{
if(node == null)
return null;
if(clonedMap.containsKey(node))
return clonedMap.get(node);
// Create a new node with the same value.
Node newNode = new Node(node.val);
// Store it in the map.
clonedMap.put(node, newNode);
for(Node u : node.neighbors)
{
// Recursively clone all neighbors and add them to the clone’s neighbor list.
Node nextNode = dfs(u, clonedMap);
newNode.neighbors.add(nextNode);
}
return newNode;
}
}

RAW Paste Data Copied

/*
Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/

class Solution {
    public Node cloneGraph(Node node) {
        // Create a map to store original nodes -> cloned nodes.
        Map<Node, Node> clonedMap = new HashMap<>();

return dfs(node, clonedMap);
    }

public Node dfs(Node node, Map<Node, Node> clonedMap)
    {
        if(node == null)
            return null;
        
        if(clonedMap.containsKey(node))
            return clonedMap.get(node);
        
        // Create a new node with the same value.
        Node newNode = new Node(node.val);
        // Store it in the map.
        clonedMap.put(node, newNode);

for(Node u : node.neighbors)
        {
            // Recursively clone all neighbors and add them to the clone’s neighbor list.
            Node nextNode = dfs(u, clonedMap);
            newNode.neighbors.add(nextNode);
        }
        return newNode;
    }
}