44. Copy List with Random Pointer

Medium · Linked List

A linked list is given where each node contains an integer value and a random pointer that can point to any node in the list (or null). Create a deep copy of this list such that the copied list has its own set of nodes with the same values and random pointer structure, but no shared references with the original list.

The input is a linked list represented as an array of objects, where each object has a `val` (integer) and `random` (index of the node it points to, or -1 for null). Return the copied list in the same format.

Examples

Example 1
Input: [{"val": 7, "random": 1}, {"val": 13, "random": 0}, {"val": 11, "random": 4}, {"val": 10, "random": 2}, {"val": 1, "random": 0}]
Output: [{"val": 7, "random": 1}, {"val": 13, "random": 0}, {"val": 11, "random": 4}, {"val": 10, "random": 2}, {"val": 1, "random": 0}]
Explanation: A list of 5 nodes where node 0 (val=7) has random pointing to node 1, node 1 (val=13) points back to node 0, etc. The copy preserves all these relationships.
Example 2
Input: [{"val": 1, "random": -1}]
Output: [{"val": 1, "random": -1}]
Explanation: A single node with no random pointer (null). The copy is a single independent node.

Constraints