public RandomListNode copyRandomList(RandomListNode head) {
if(head==null)
return head;
HashMap<RandomListNode,RandomListNode> map = new HashMap<RandomListNode,RandomListNode>();
RandomListNode first = head;
RandomListNode nHead = new RandomListNode(first.label);
RandomListNode second = nHead;

while(first!=null){
if(first.next!= null){
RandomListNode temp = new RandomListNode(first.next.label);
second.next = temp;
}
map.put(first,second);
second.random = first.random;
first = first.next;
second = second.next;
}
second = nHead;
while(second!=null){
second.random = map.get(second.random);
second = second.next;
}
return nHead;
}




public RandomListNode copyRandomList(RandomListNode head) {
        if(head == null) return head;
         RandomListNode ptr = head;
         // make copies for all nodes
         while(ptr != null) {
           RandomListNode copy = new RandomListNode(ptr.label);
           copy.next = ptr.next;
           ptr.next = copy;
           ptr = copy.next;
          }
         // setup random node links
           ptr = head;
           while(ptr != null){
              RandomListNode copy = ptr.next;
              if(ptr.random != null)
              copy.random = ptr.random.next;
              ptr = copy.next;
            }
    // separate nodes
    RandomListNode orig=head;
    RandomListNode copyCur=head.next;
    RandomListNode copyHead=head.next;

    while(orig.next != null && copyCur.next != null){
        orig.next=orig.next.next;
        copyCur.next=copyCur.next.next;
        orig=orig.next;
        copyCur=copyCur.next;
    }
    orig.next=null;

    return copyHead;
}