You are given the head of a linked list of length n where each node contains an additional pointer random, which may point to any node in the list or be null.

Construct a deep copy of the list. The deep copy must consist of exactly n new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointers of the new nodes should point to new nodes in the copied list such that the structural relationships of the original list are preserved. None of the pointers in the copied list should reference nodes in the original list.

Return the head of the copied linked list.

Constraints:

• $0 \leq$ n $\leq 1000$

• $-10^4 \leq$ Node.val $\leq 10^4$

• Node.random is null or points to a node in the linked list.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.