Leetcode and Lintcode

Copy List with Random Pointer

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.

Solution:

Use a hash to record each node in the origin list as a key
The value is the deep copy of corresponding node.
Go through the list, for each node and random reference, check the map,
if the key was included in the map, get the value, or create a new node with the same label, and put it into the map.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/*************************************************************************
	> File Name: CopyListwithRandomPointer.java
	> Author: Yao Zhang 
	> Mail: psyyz10@163.com 
	> Created Time: Thu 19 Nov 23:02:20 2015
 ************************************************************************/

public class CopyListwithRandomPointer{
	public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null)
            return null;
            
        HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
        RandomListNode dummy = new RandomListNode(-1);
        RandomListNode prev = dummy, newNode;
        
        
        while (head != null){
            if (map.containsKey(head))
                newNode = map.get(head);
            else{
                newNode = new RandomListNode(head.label);
                map.put(head,newNode);
            }
            prev.next = newNode;
            
            if (head.random != null){
                if (map.containsKey(head.random))
                    newNode.random = map.get(head.random);
                else{
                    newNode.random = new RandomListNode(head.random.label);
                    map.put(head.random, newNode.random);
                }
                    
            }
            
            prev = prev.next;
            head = head.next;
        }
        
        return dummy.next;
    }
}