Simple solution [JAVA] Time: O(n), Space: O(1)

#1

Algo: Use 2 maps 1. <pointer, position> 2. <position, pointer>. Copy next pointers in 1st scan, and fill map1 & map2. In next scan, fix copy random pointers.

NOTE: mapping by node value will fail if there are duplicates. So, use a unique position on the map.

public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        Map<RandomListNode, Integer> hMap1 = new HashMap<>();
        Map<Integer, RandomListNode> hMap2 = new HashMap<>();
        RandomListNode result = new RandomListNode(0);
        RandomListNode p1 = head, p2 = result;
        int pos = 1;
        while(null != p1) {
            hMap1.put(p1, pos);
            p2.next = new RandomListNode(p1.label);
            p1 = p1.next;
            p2 = p2.next;
            hMap2.put(pos, p2);
            pos++;
        }
        
        p1 = head;
        p2 = result.next;
        pos = 1;
        while(null != p1) {
            // RandomListNode 
            p2.random = hMap2.get(hMap1.get(p1.random));
            p1 = p1.next;
            p2 = p2.next;
        }
        return result.next;
    }
}