Deep copy a linked list with random pointers

## Problem You are given the head of a linked list where each node has: - `val`: integer value - `next`: pointer to the next node (or `null`) - `random`: pointer to any node in the list (or `null`) Return the head of a **deep-copied** linked list such that: - The copied list contains entirely new nodes (no node is shared with the original). - The `next` and `random` structure is preserved. ## Constraints - `0 <= n <= 10^5` - `-10^4 <= val <= 10^4` ## Requirements - Discuss time and space complexity. - Provide an approach that runs in **O(n)** time. - Explore an approach that uses **O(1)** extra space (not counting the output list itself), and explain tradeoffs vs. using a hash map. ## Example (conceptual) If node A’s `random` points to node C in the original list, then A’ (copy of A) must have `random` pointing to C’ (copy of C).