/*
this kep point is that:
- use the address of the node as the key in the hash
- the value part of the hash should be a new node, since we want to create a deep copy
- after the the deep copy, we need to deal with the next&random pointer 
- for next&random pointer, first, we need to find the node by using the address, then for that node's next we use the original node.next, since node.next is a address pointer which points the node stuff within the hash!!! this is the key-point!!!!
*/
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) {
            return null;
        }

        HashMap<RandomListNode, RandomListNode> hs = new HashMap<RandomListNode,RandomListNode>();
        RandomListNode cur = head;

        //just make the node space copy
        while (cur!=null){
            hs.put(cur, new RandomListNode(cur.label));
            cur = cur.next;
        }

        //deal with the next and random pointer
        RandomListNode temp = head;
        while (temp!=null) {
            hs.get(temp).next = hs.get(temp.next);
            hs.get(temp).random = hs.get(temp.random);
            temp = temp.next;
        }

        return hs.get(head);

    }
}