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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        int length = getRandomList(head);
        if(length == 0)
            return NULL;
        int index = 0;
        RandomListNode * headb1 = head;
        map<RandomListNode *, int> map_ri;
        map_ri.clear();
        while(head != NULL) {
            map_ri.insert(map<RandomListNode *, int>::value_type(head, index++));
            head = head->next;
        }
        int *pos = new int[length];
        map<RandomListNode *, int>::iterator itri;
        index = 0;
        head = headb1;
        while(head != NULL) {
            itri = map_ri.find(head->random);
            if(itri == map_ri.end())
                pos[index++] = -1;
            else
                pos[index++] = itri->second;
            head = head->next;
        }
        head = headb1;
        map<int, RandomListNode *> map_r;
        map_r.clear();
        index = 0;
        RandomListNode *copy = new RandomListNode(head->label);
        RandomListNode *copymove = copy;
        map_r.insert(map<int, RandomListNode *>::value_type(index++, copymove));
        head = head->next;
        while(head != NULL) {
            RandomListNode * tmp = new RandomListNode(head->label);
            copymove->next = tmp;
            copymove = copymove->next;
            map_r.insert(map<int, RandomListNode *>::value_type(index++, copymove));
            head = head->next;
        }
        copymove = copy;
        index = 0;
        while(copymove != NULL) {
            map<int, RandomListNode *>::iterator it = map_r.find(pos[index++]);
            if(it == map_r.end())
                copymove->random = NULL;
            else
                copymove->random = it->second;
            copymove = copymove->next;
        }
        return copy;
    }
private:
    int getRandomList(RandomListNode *head) {
        int length = 0;
        while(head != NULL) {
            head = head->next;
            length++;
        }
        return length;
    }
};