solved "Copy List with Random Pointer" on LeetCode (one-pass AC! reminds me of copying GC) http://oj.leetcode.com/problems/copy-list-with-random-pointer/

RandomListCopy.java

/**
 * 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;
        RandomListNode iter = head;
        RandomListNode newHead = new RandomListNode(head.label);
        RandomListNode newIter = newHead;
        Map<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
        // first pass, copy object
        do {
            map.put(iter, newIter);
            iter = iter.next;
            if (iter != null)
                newIter.next = new RandomListNode(iter.label);
            newIter = newIter.next;
        } while (iter != null);
        
        iter = head;
        newIter = newHead;
        // second pass, modify random pointer
        while (iter != null) {
            if (iter.random != null)
                newIter.random = map.get(iter.random);
            iter = iter.next;
            newIter = newIter.next;
        }
        return newHead;
    }
}