// 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.

/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */

public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
    	if(head == null) return head;

    	HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
    	RandomListNode runner = head;

    	while(runner != null){
    		RandomListNode copy = new RandomListNode(runner.label);
    		map.put(runner, copy);
    		runner = runner.next;
    	}    

    	runner = head;

    	while(runner != null){
    		map.get(runner).next = map.get(runner.next);
    		map.get(runner).random = map.get(runner.random);
    		runner = runner.next;
    	}

    	return map.get(head);
    }
}
@@ -1011,8 +1011,1918 @@
 %0A    %7D%0A%7D
+%0A%0A/**%0A * Definition for singly-linked list with a random pointer.%0A * class RandomListNode %7B%0A *     int label;%0A *     RandomListNode next, random;%0A *     RandomListNode(int x) %7B this.label = x; %7D%0A * %7D;%0A */%0Apublic class Solution %7B%0A    public RandomListNode copyRandomList(RandomListNode head) %7B%0A        // solution using constant space%0A        // the idea is that: interleaving original list by inserting%0A        // copied nodes into it during the first iteration,%0A        // then go through the list for second time, update the random%0A        // pointer%0A        // finally iterate the list for third time to revert back original%0A        // list and generate the new copied one.%0A        if (head == null) %7B%0A            return head;%0A        %7D%0A        %0A        RandomListNode runner = head;%0A        // insert copied nodes into list%0A        while (runner != null) %7B%0A            RandomListNode copied = new RandomListNode(runner.label);%0A            RandomListNode next = runner.next;%0A            runner.next = copied;%0A            copied.next = next;%0A            runner = next;%0A        %7D%0A        // update random pointer%0A        runner = head;%0A        RandomListNode copiedRunner = runner.next;%0A        while (runner != null) %7B%0A            if (runner.random != null) %7B%0A                copiedRunner.random = runner.random.next;%0A            %7D%0A            runner = copiedRunner.next;%0A            if (runner != null) %7B%0A                copiedRunner = runner.next;%0A            %7D%0A        %7D%0A%0A        RandomListNode copiedHead = head.next;%0A        runner = head;%0A        copiedRunner = copiedHead;%0A        // revert back%0A        while (runner != null) %7B%0A            runner.next = copiedRunner.next;%0A            runner = runner.next;%0A            if (runner != null) %7B%0A                copiedRunner.next = runner.next;%0A                copiedRunner = copiedRunner.next;%0A            %7D%0A        %7D%0A%0A        return copiedHead;%0A    %7D%0A%7D%0A

update copy list with random pointer solution