Clone Linked List with Random + Next Pointer

Requirements Every list element contains val, next, and random; the random pointer can target any list node or be null. Produce an independent duplicate in which all pointers refer only to freshly created nodes, with no nodes shared with the input list. Implement copyRandomList(head: Node null) -> Node null. Be prepared to compare an O(n)-auxiliary-space hashmap method with the O(1)-auxiliary-space clone-interleaving technique. A recursive memoized approach (clone(node)…