public RandomListNode copyRandomList2(RandomListNode head) {
        if (head == null) return null;

        //duplicate each node
        RandomListNode x = head;
        while (x != null) {
            RandomListNode copy = new RandomListNode(x.label);
            copy.next = x.next;
            x.next = copy;
            x = copy.next;
        }

        //set random to duplicated nodes
        x = head;
        while (x != null) {
            RandomListNode copy = x.next;
            if (x.random != null)
                copy.random = x.random.next;
            x = copy.next;
        }

        //remove original nodes
        RandomListNode fakeHead = new RandomListNode(0);
        RandomListNode Head = fakeHead;
        x = head;
        while (x != null) {
            RandomListNode next = x.next.next;
            RandomListNode copy = x.next;
            fakeHead.next = copy;
            fakeHead = fakeHead.next;
            x.next = next;
            x = next;
        }

        return Head.next;

    }
This duplicates each node next to original one. on the second round of iteration it sets random elements
on the third round of iteration we remove original ones and duplicates are left. 3 iteration and no extra space
src/problems/hard/CopyListwithRandomPointer.java