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).