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 /** 2  * Definition for singly-linked list with a random pointer. 3  * class RandomListNode { 4  *     int label; 5  *     RandomListNode next, random; 6  *     RandomListNode(int x) { this.label = x; } 7  * }; 8  */ 9 public class Solution {10     public RandomListNode copyRandomList(RandomListNode head) {11         if (head == null) return null;12         RandomListNode dummy = new RandomListNode(0);13         RandomListNode scan = dummy;14         RandomListNode cur = head;15         HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();16         while (cur != null) {17             scan.next = new RandomListNode(cur.label);18             map.put(cur, scan.next);19             cur = cur.next;20             scan = scan.next;21         }22         cur = head;23         scan = dummy;24         while (cur != null) {25             scan.next.random = map.get(cur.random);26             cur = cur.next;27             scan = scan.next;28         }29         return dummy.next;30     }31 }