-
Notifications
You must be signed in to change notification settings - Fork 0
/
CopyListwithRandomPointer.hpp
61 lines (48 loc) · 1.14 KB
/
CopyListwithRandomPointer.hpp
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
//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.
#include <cstdlib>
#include <map>
/**
* 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) {}
* };
*/
struct RandomListNode {
int label;
RandomListNode *next, *random;
RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
};
class Solution
{
public:
RandomListNode *copyRandomList(RandomListNode *head)
{
if (nullptr == head)
return nullptr;
std::map<RandomListNode*,RandomListNode*> mpNode;
RandomListNode* p = head;
while (nullptr != p)
{
RandomListNode* tmp = new RandomListNode(p->label);
tmp->next = p->next;
tmp->random = p->random;
mpNode.insert(std::make_pair(p, tmp));
p = p->next;
}
p = mpNode[head];
while (nullptr != p)
{
p->next = mpNode[p->next];
p->random = mpNode[p->random];
p = p->next;
}
return mpNode[head];
}
};