A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

1. HashMap version

public class Solution {
    /**
     * @param head: The head of linked list with a random pointer.
     * @return: A new head of a deep copy of the list.
     */
    public RandomListNode copyRandomList(RandomListNode head) {
        // write your code here

        if (head == null) {
            return null;
        }

        RandomListNode dummy = new RandomListNode(0);
        dummy.next = head;
        HashMap<RandomListNode, RandomListNode> copyMap = new HashMap<>();


        RandomListNode newHead = new RandomListNode(head.label);
        RandomListNode dummyNew = new RandomListNode(0);
        dummyNew.next = newHead;
        copyMap.put(head, newHead);

        while (head.next != null) {
            newHead.next = new RandomListNode(head.next.label);
            copyMap.put(head.next, newHead.next);
            head = head.next;
            newHead = newHead.next;
        }

        head = dummy.next;
        while (head != null) {
            RandomListNode curr = copyMap.get(head);
            curr.random = copyMap.get(head.random);

            head = head.next;
        }

        return dummyNew.next;

    }
}

1. O(1) space complexity

public class Solution {
    /**
     * @param head: The head of linked list with a random pointer.
     * @return: A new head of a deep copy of the list.
     */
    public RandomListNode copyRandomList(RandomListNode head) {
        // write your code here
        if (head == null) {
            return head;
        }

        //insert the copied list into the original list

        RandomListNode dummy = new RandomListNode(0);
        dummy.next = head;

        //1->1'->2->2'->3->3'->4->4'->5->5'
        while (head != null) {
            RandomListNode newNode = new RandomListNode(head.label);
            RandomListNode temp = head.next;
            head.next = newNode;
            newNode.next = temp;

            head = head.next.next;
        }

        head = dummy.next;
        RandomListNode newHead = head.next;

        while (head != null) {


            if (head.random != null) {
                newHead.random = head.random.next;
            }

            head = newHead.next;

            if (head != null) {
                newHead.next = head.next;
                newHead = newHead.next;
            }


        }

        return dummy.next.next;


    }
}