Use a hash map to link each original node to its copy. Do it in two passes.
Pass : walk through the original list and create a clone of each node (just the value, no pointers yet). Store the mapping original -> clone in a hash map.
Pass : walk through the original list again. For each node, set the clone's next to map[original.next] and the clone's random to map[original.random].
By the time you wire pointers in pass , every clone already exists in the map. You never have the "target not yet created" problem because you built all nodes first.