-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy List with Random Pointer.cpp
86 lines (82 loc) · 2.09 KB
/
Copy List with Random Pointer.cpp
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<iostream>
#include<string>
#include<vector>
#include <cctype>
#include<algorithm>
#include<math.h>
#include<unordered_map>
using namespace std ;
typedef struct ListNode{
int val;
ListNode * next;
} ListNode;
struct RandomListNode {
int label;
RandomListNode *next, *random;
RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
};
class Solution {
public:
RandomListNode *copyRandomList(RandomListNode *head) {
unordered_map<RandomListNode*,RandomListNode*> map;
RandomListNode *iter,*node2cp,*node,*noderd;
RandomListNode *res=new RandomListNode(0);
unordered_map<RandomListNode*,RandomListNode*>::iterator mapiter;
if(head==NULL)
return NULL;
res->label=head->label;
for(iter=head,node2cp=res;iter;iter=iter->next){
if(iter!=head){
mapiter=map.find(iter);
if(mapiter==map.end()){
node=new RandomListNode(iter->label);
node2cp->next=node;
map.insert(make_pair(iter,node));
}
else{
node2cp->next=mapiter->second;
//node=node->next;
}
node2cp=node2cp->next;
}
//for(noderd=iter->random;noderd;noderd=noderd->random)
if(iter->random){
mapiter=map.find(iter->random);
if(mapiter==map.end()){
node=new RandomListNode(iter->random->label);
node2cp->random=node;
map.insert(make_pair(iter->random,node));
}
else
node2cp->random=mapiter->second;
}
}
return res;
}
void print()
{
RandomListNode* A=new RandomListNode(1);
RandomListNode* B=new RandomListNode(2);
RandomListNode* C=new RandomListNode(3);
RandomListNode* D=new RandomListNode(4);
RandomListNode* E=new RandomListNode(5);
A->next=B;
A->random=C;
B->next=C;
B->random=A;
C->next=D;
C->random=E;
RandomListNode *res=copyRandomList(A);
cout<<res->random->label<<endl;
cout<<res->next->label<<endl;
cout<<res->random->next->label<<endl;
}
};
int main()
{
Solution test;
// cout<<test.Low("A man, a plan, a canal: Panama")<<endl;
test.print();
// cout<<atoi("2147483648")<<endl;
system("pause");
}