题目描述
给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。
要求返回这个链表的 深拷贝。
题解
和之前的clone graph很相似，使用一个queue用来遍历所有节点，是用一个unordered_map来记录被访问过的节点(key)以及clone得到的新节点(value)。
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
| Node* copyRandomList(Node* head) {
if (!head)return NULL;
queue<Node*>q;
unordered_map<Node*, Node*> m;
m[head] = new Node(head->val);
q.push(head);
Node *t1, *t2, *t3;
while (!q.empty())
{
t1 = q.front();
q.pop();
if (!m.count(t1))
m[t1] = new Node(t1->val);
t2 = t1->next;
if (t2)
{
if (!m.count(t2))
m[t2] = new Node(t2->val);
m[t1]->next = m[t2];
q.push(t2);
}
t3 = t1->random;
if (t3)
{
if (!m.count(t3))
m[t3] = new Node(t3->val);
m[t1]->random = m[t3];
}
}
return m[head];
}
|