https://oj.leetcode.com/problems/copy-list-with-random-pointer/

http://blog.csdn.net/linhuanmars/article/details/22463599

/**
 * 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 null;
        
        Map<RandomListNode, RandomListNode> map = new HashMap<>();
        RandomListNode old = head;
        RandomListNode precopied = null;
        while (old != null)
        {
            // Copy
            RandomListNode copied = new RandomListNode(old.label);
            if (precopied != null)
                precopied.next = copied;
            precopied = copied;
            map.put(old, copied);
            
            old = old.next;
        }
        
        RandomListNode newhead = map.get(head);
        while (head != null)
        {
            map.get(head).random = map.get(head.random);
            head = head.next;
        }
        
        return newhead;
    }    
}

[LeetCode]138 Copy List with Random Pointer