Clone Graph: the idea to remember.

The core insight

Create and register a clone before recursively copying its neighbors.

Why it works

The map gives every original node exactly one clone. Registering first lets back edges reuse the existing clone instead of recursing forever.

The mistake to avoid

Map by node identity, not only value, and never return an original neighbor.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

Node cloneGraph(Node start) {
    return cloneNode(start, new HashMap<>());
}
Node cloneNode(Node node, Map<Node, Node> copies) {
    if (node == null) return null;
    if (copies.containsKey(node)) return copies.get(node);
    Node copy = new Node(node.val);
    copies.put(node, copy); // Register before visiting cycles.
    for (Node neighbor : node.neighbors) copy.neighbors.add(cloneNode(neighbor, copies));
    return copy;
}

Make the next connection