Deep Clone II

Implement deepCloneII(value) — a deep clone that walks nested objects and arrays and correctly handles circular references and shared substructure. The medium version of this problem assumed a tree-shaped input; this one assumes a graph. A node can reference any other node, including itself, and any two pointers to the same node must remain a single shared node in the output.

The new dimension here is the visited map. Every time the recursion enters an object or array, it records that original together with the fresh clone it just allocated. The next time the same original shows up — whether from a cycle back to an ancestor, or from two siblings both pointing at the same node — the recursion returns the existing clone instead of allocating a new one. Cycles and DAGs fall out of the same line of code.

Signature

// Returns a deep copy that mirrors the input's reference graph: cycles
// in the input become cycles in the output, shared nodes in the input
// stay shared in the output. The result shares no object references
// with the input.
function deepCloneII<T>(value: T): T;

Examples

// A self-cycle is preserved within the clone, not back to the original.
const a = {};
a.self = a;
const c = deepCloneII(a);
c !== a;          // true  — top-level reference is new
c.self === c;     // true  — cycle preserved within the clone graph
c.self === a;     // false — never points back at the source

// Shared substructure (DAG) — both keys point to the SAME inner node.
// The clone preserves that sharing: one clone of x, referenced twice.
const x = { n: 1 };
const obj = { a: x, b: x };
const c = deepCloneII(obj);
c.a === c.b;      // true  — sharing preserved
c.a !== x;        // true  — but it's a fresh clone, not the source

// A cycle one level deep: child loops back to grandparent.
const root = { name: 'root' };
const child = { name: 'child' };
root.child = child;
child.parent = root;
const c = deepCloneII(root);
c.child.parent === c;       // true — child loops back to the clone of root
c.child.parent !== root;    // true — and never to the original

Notes

• Scope. This implementation handles primitives, plain objects, arrays, cycles, and shared substructure. Date, RegExp, Map, Set, TypedArray, class instances with custom prototypes, and symbol-keyed properties are out of scope — see the solution's "Going further" for how each would extend.
• Cycles must be preserved, not detected-and-thrown. A cycle in the input becomes a cycle in the output, wired entirely inside the clone graph. That is different from cycle detection (just throw on a cycle, like JSON.stringify does), which is not the goal here.
• Shared nodes must stay shared. If two pointers reference one node in the input, two pointers must reference one clone in the output — not two separate clones. The visited map handles cycles and DAGs with the same lookup.
• Only own enumerable string keys. Use Object.keys — don't walk the prototype chain, don't copy inherited properties, don't copy symbol keys.
• Do not use JSON.parse(JSON.stringify(...)). It throws on cycles, drops undefined, mangles Date, and loses functions. The whole point of this question is handling cases that defeat that one-liner.