37. Copy List with Random Pointer

You’re interviewing for a backend or data engineering role at a FAANG-level company. The interviewer describes a real product scenario:

A large-scale backend system stores complex in-memory structures that represent workflows, graphs of objects, or cached entities. Each entity is stored in a linked list where every node has:

• next pointer for the normal sequence
• random pointer that can reference any node in the list (or be null)

Before deploying a new service version, the platform needs to safely duplicate this structure for:

• snapshotting system state
• creating isolated test environments
• rollback safety
• sandbox execution

To do this correctly, you must create a deep copy of the list, meaning new nodes must be created and pointers must point only within the new list.

This is a common practice coding problem for DSA question might ask in Google, Amazon, Netflix, Meta, Apple, Microsoft, Uber, and Bloomberg interviews.

Your Task

Given the head of a linked list where each node has a next pointer and a random pointer, return the head of a deep copy of the list.

A deep copy means:

• Every node in the new list is a newly created node
• next and random pointers in the new list point to nodes in the new list
• No pointer in the new list should reference nodes in the original list

Input Format

• head: head of the linked list

Each node is defined as:

Node { int val; Node next; Node random; }

Output Format

• Return the head of the deep-copied linked list

Examples

Constraints

• 0 <= number of nodes <= 10,000
• -10^4 <= Node.val <= 10^4
• Node.random may be null or point to any node in the list