解题思路：1.暴力求解。2.创建map，存储每个指针和它的位置；创建vector v，存储新链表的每个节点。遍历一遍原始链表和新建链表，找出原始链表中当前节点的随机指针在map中映射的位置i，则新建链表中当前节点的随机指针指向v[i]。
链表l: a -> b ->c -> d (随机节点对应：a -> b、b -> d、c -> d)
----- -----
----------
映射m: (a,0) (b,1) (c,2) (d,3)
新建链表l1: a' -> b' -> c' -> d'
vector v:[a',b',c',d']
遍历l:
比如当前节点a，a随机指向的节点a->random。
在m中找到a->random的位置i。
则a'的随机节点也映射到l1链表中的第i个节点v[i]。
代码如下：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
64
65/**
* Definition for singly-linked list with a random pointer.
* struct RandomListNode {
* int label;
* RandomListNode *next, *random;
* RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
* };
*/
class Solution {
public:
RandomListNode *copyRandomList(RandomListNode *head) {
if(head == NULL) return NULL;
unordered_map<RandomListNode*,int> m;
vector<RandomListNode*> new_node_vector;
RandomListNode *cur = head;
RandomListNode *new_dummy = new RandomListNode(-1);
RandomListNode *new_cur = new_dummy;
int i = 0;
while(cur != NULL)
{
m[cur] = i++;
// original_vector.push_back(cur);
RandomListNode *new_node = new RandomListNode(cur->label);
new_node_vector.push_back(new_node);
new_cur->next = new_node;
new_cur = new_node;
cur = cur->next;
}
cur = head;
new_cur = new_dummy->next;
while(cur != NULL)
{
RandomListNode *cur_random = cur->random;
if(cur_random != NULL)
{
int position = m[cur_random];
// cout<<position<<endl;
new_cur->random = new_node_vector[position];
}
cur = cur->next;
new_cur = new_cur->next;
}
// for(auto it = original_vector.begin(), new_it = new_node_vector.begin(); it != original_vector.end() && new_it != new_node_vector.end(); it++,new_it++)
// {
// if((*it)->random != NULL)
// {
// int position = m[(*it)->random];
// (*new_it)->random = new_node_vector[position];
// }
// else
// {
// (*new_it)->random = NULL;
// }
// }
return new_dummy->next;
}
};
运行结果：136ms，超过23.46%