Deep-Copy a Linked List Whose Nodes Also Carry a Random Pointer

Each node of a singly linked list has a value, a `next` pointer and a `random` pointer. The `random` pointer can point to any node of the list, including the node itself, or be `None`. Write a function that returns a deep copy of the list: a list of entirely new nodes with the same values, whose `next` and `random` pointers point to the corresponding new nodes and never to nodes of the original list. ```python class Node: def __init__(self, val, next=None, random=None): self.val = val self.next = next self.random = random def copy_list(head: "Node | None") -> "Node | None": ... ``` ```text original: A(7) -> B(13) -> C(11) -> None random: A -> None, B -> A, C -> C copy: A'(7) -> B'(13) -> C'(11) -> None random: A' -> None, B' -> A', C' -> C' ``` ```hint Pointers to nodes not copied yet When you copy a node, its random pointer may lead to a node further along the list. Think about how you could find the copy of any original node once that copy exists. ``` ```hint Prove the copy is deep Think about what a test must check so that a copy which secretly points back into the original list fails. ``` ### Constraints and Clarifications - The list can be empty. - Several nodes can have their `random` pointers on the same node, and a `random` pointer can point backward or forward. - Values can repeat, so a node cannot be identified by its value. - The original list must be unchanged when the function returns. ### Clarifying Questions - Is extra memory proportional to the length of the list acceptable, or should the copy use constant extra space besides the new nodes? - May the original list be modified temporarily during the copy, or do other threads read it at the same time? - How long can the list be, so that recursion depth becomes a concern? ### What a Strong Answer Covers - A correct way to find the copy of any original node, including random targets not yet copied - Correct results for an empty list, `None` random pointers, self-pointers and shared targets - Time and extra-space complexity, with an iterative approach that cannot overflow the stack - A test that proves the copy shares no node with the original and that the original is unchanged ### Follow-up Questions - Make the copy using constant extra space besides the new nodes. - The structure becomes a general graph in which each node has a list of neighbors. How does your approach change? - Other threads read the original list while you copy it. Which approach is still safe?