Space Efficient Solution

So now we cannot use any extra lists or hashmaps that would increase the space complexity. What do we do in this case?

Well, let's assume that the linked list is not read-only, but we can modify it as well. The idea is to add new nodes to the list and shift pointers such that the new nodes point to each other in the same state as the original list. In other words,

• Create a copy of the first node, and insert it between the first and second node of the original list. Now create a copy of the second node, and insert it between the second and third node. Add duplicate nodes in this fashion for the entire list.
• Next, copy the random pointer of each node, and make them point to other nodes in the same way as the original list.
  
• Finally, separate the original and duplicate nodes by adjusting the pointers in the following manner (the next pointer will move to skip a node to point to the original list node, same for copy list).

1originalList.next = originalList.next.next;
2copyList.next = copyList.next.next;