A Simple Solution

Copying a linked list is an easy task. Copy the head node, then create a new node with the same value as its corresponding node in the original list. Then, set the next pointer of the node to the newly created node, and by repeating this process, you can copy all nodes. On the other hand, dealing with the random pointer of the linked list is a little tricky. For each node, we need to remember where the random pointer points to. This means we need to save information, and for that, we can use hashmaps to remember the copied nodes. Essentially, there are just two steps:

1. Create a copy of all the nodes of the linked list. Fill the hashmap for each node by saving its information
2. Traverse through the copied list, and set the random pointer of each node according to the hashmap.

1copyHead = Node(head.val)
2
3while currentNode:
4    newNode = Node(currentNode.val)
5    hashmap[currentNode] = newNode
6    currentNode = currentNode.next

Now, this approach seems fine, but there is one problem. Using a hashmap would mean we are using additional space of O(n). That does not fit well with the constraint of our problem, which requires us to solve without using any additional space.