The problem. You're given one node of a connected, undirected graph. Each Node has a val and a list of neighbors. Return a deep copy of the whole graph: brand-new nodes with the same values, wired to each other exactly like the originals — and not one pointer into the old graph.
adjList = [[2,4],[1,3],[2,4],[1,3]] -> [[2,4],[1,3],[2,4],[1,3]]
(same shape, all new nodes)
adjList = [[]] -> [[]] (one node, no neighbours)
adjList = [] -> [] (no graph: null in, null out)adjList[i] lists the neighbours of the node with value i + 1; you're handed the node with value 1.
Walk every node with DFS or BFS. When you first meet an original node, create its copy. Wire each copy's neighbors to the copies of the original's neighbours.
The trap is cycles: node 1's neighbour 2 has neighbour 1 again. A hash map from original → copy solves both problems at once — it's the visited set (a node in the map has been met), and it's how you find the copy to wire to. Put each copy in the map before walking its neighbours, so a cycle that leads back finds it there instead of copying forever.
function cloneGraph(node) { if (node === null) return null; const copies = new Map(); // original node -> its copy const clone = (orig) => { if (copies.has(orig)) return copies.get(orig); // met before (maybe round a cycle): reuse it const copy = new Node(orig.val); copies.set(orig, copy); // record it BEFORE the neighbours, so cycles stop here for (const nb of orig.neighbors) copy.neighbors.push(clone(nb)); return copy; }; return clone(node);}Time O(V + E), space O(V). Each node is copied once and each edge is wired once from each end. The map holds V entries, and the recursion can be V deep.
The same map, filled by a queue. Create a node's copy the first time you see it as a neighbour, and add it to the queue; every edge you look at becomes one wire between two copies.
The copy grows beside the original. Each edge looked at becomes one wire between two copies.
function cloneGraph(node) { if (node === null) return null; const copies = new Map([[node, new Node(node.val)]]); // original -> copy const queue = [node]; let head = 0; while (head < queue.length) { const orig = queue[head++]; for (const nb of orig.neighbors) { if (!copies.has(nb)) { copies.set(nb, new Node(nb.val)); // first time we see nb: make its copy queue.push(nb); } copies.get(orig).neighbors.push(copies.get(nb)); // wire the copied edge } } return copies.get(node);}Time O(V + E), space O(V). The same work, without recursion.
