DIY: Copy List with Random Pointer

Problem statement

You are given a linked list where each node contains an additional pointer called random. This pointer can point towards any node in the list or none. Your task is to create a function that takes the head of this linked list, creates a deep copy of the list, and then outputs the head of the copied list.

Input

The function’s input will be the head of a linked list with a random pointer. This head will be of type Node. The Node class contains an integer val, a next node pointer, and a random node pointer. The following is an example input: