题目

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.

思路
Given List A
First Pass
List B = Clone List A based next pointer
When cloning B, build the following two maps
First map, maps node in A to corresponding nodes in B
Second map, maps source and target of some random pointer in A

Second Pass
Iterate through the list B
Let's say current node is called curr
To add random pointer for curr, add edge (first_map.get(curr), first_map.get(second_map.get(curr)))

答案

public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if(head == null) return null;
        HashMap<RandomListNode, RandomListNode> clone_map = new HashMap<RandomListNode, RandomListNode>();
        HashMap<RandomListNode, RandomListNode> ranptr_map = new HashMap<RandomListNode, RandomListNode>();
        
        // First pass, clone list
        RandomListNode cloned = null, list1 = head, list2 = null;
        while(list1 != null) {
            if(cloned == null) {
                cloned = new RandomListNode(list1.label);
                list2 = cloned;
            }
            else {
                list2.next = new RandomListNode(list1.label);
                list2 = list2.next;
            }
            clone_map.put(list1, list2);
            ranptr_map.put(list1, list1.random);
            list1 = list1.next;
        }
        // Second pass, add random pointers
        list1 = head;
        list2 = cloned;
        while(list1 != null) {
            list2.random = clone_map.get(ranptr_map.get(list1));
            list2 = list2.next;
            list1 = list1.next;
        }
        return cloned;
    }
}

另一种简单的实现思路(在面试中用这种方法更容易实现)

public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) {
            return null;
        }
        
        final Map<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();

        RandomListNode cur = head;
        while(cur != null) {
            map.put(cur, new RandomListNode(cur.label));
            cur = cur.next;
        }
        
        for (Map.Entry<RandomListNode, RandomListNode> entry : map.entrySet()) {
            final RandomListNode newNode = entry.getValue();
            newNode.next = map.get(entry.getKey().next);
            newNode.random = map.get(entry.getKey().random);
        }
        
        return map.get(head);
    }
}