Re: 【承诺凡顶贴到偶数页即奔一张新照片】！～# PhotoGear - 摄影器材
e*s
1 楼
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.
下面注释里面是别人写的能跑过的 上面的是我的 到现在都改得几乎一模一样了
可是还是超时
/**
* 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) {
unordered_map myMap;
if (NULL == head) return NULL;
RandomListNode* myhead = NULL;
DFS(head,myhead,myMap);
return myhead;
}
void *DFS(RandomListNode *DFSOldHead, RandomListNode *&DFSMyHead,
unordered_map DFSmyMap){
if (NULL == DFSOldHead) return NULL;
DFSMyHead = new RandomListNode(DFSOldHead->label);
if( DFSmyMap.find(DFSOldHead) == DFSmyMap.end() ){
DFSmyMap[DFSOldHead] = DFSMyHead;
}
if (DFSOldHead -> next){
if (DFSmyMap.end() == DFSmyMap.find(DFSOldHead -> next)){
DFS(DFSOldHead -> next, DFSMyHead->next, DFSmyMap);
}
else{
DFSMyHead -> next = DFSmyMap[DFSOldHead -> next];
}
}
if (DFSOldHead -> random){
if (DFSmyMap.end() == DFSmyMap.find(DFSOldHead -> random)){
DFS(DFSOldHead -> random, DFSMyHead->random, DFSmyMap);
}
else{
DFSMyHead -> random = DFSmyMap[DFSOldHead -> random];
}
}
}
};
/*
class Solution {
public:
RandomListNode *copyRandomList(RandomListNode *head) {
// Note: The Solution object is instantiated only once and is reused
by each test case.
if( head==NULL ) return NULL;
RandomListNode* newHead = NULL;
unordered_map< RandomListNode*, RandomListNode* > occur;
dfs( newHead, head, occur );
return newHead;
}
void dfs( RandomListNode*&cur, RandomListNode* node, unordered_map<
RandomListNode*, RandomListNode* >& occur ){
if( node==NULL ) return;
cur = new RandomListNode( node->label );
if( occur.find(node) == occur.end() ){
occur[node] = cur;
}
if( node->next ){
if( occur.find(node->next)==occur.end() ){
dfs( cur->next, node->next, occur );
}else{
cur->next = occur[node->next];
}
}
if( node->random ){
if( occur.find(node->random)==occur.end() ){
dfs( cur->random, node->random, occur );
}else{
cur->random = occur[node->random];
}
}
}
};
*/
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.
下面注释里面是别人写的能跑过的 上面的是我的 到现在都改得几乎一模一样了
可是还是超时
/**
* 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) {
unordered_map
if (NULL == head) return NULL;
RandomListNode* myhead = NULL;
DFS(head,myhead,myMap);
return myhead;
}
void *DFS(RandomListNode *DFSOldHead, RandomListNode *&DFSMyHead,
unordered_map
if (NULL == DFSOldHead) return NULL;
DFSMyHead = new RandomListNode(DFSOldHead->label);
if( DFSmyMap.find(DFSOldHead) == DFSmyMap.end() ){
DFSmyMap[DFSOldHead] = DFSMyHead;
}
if (DFSOldHead -> next){
if (DFSmyMap.end() == DFSmyMap.find(DFSOldHead -> next)){
DFS(DFSOldHead -> next, DFSMyHead->next, DFSmyMap);
}
else{
DFSMyHead -> next = DFSmyMap[DFSOldHead -> next];
}
}
if (DFSOldHead -> random){
if (DFSmyMap.end() == DFSmyMap.find(DFSOldHead -> random)){
DFS(DFSOldHead -> random, DFSMyHead->random, DFSmyMap);
}
else{
DFSMyHead -> random = DFSmyMap[DFSOldHead -> random];
}
}
}
};
/*
class Solution {
public:
RandomListNode *copyRandomList(RandomListNode *head) {
// Note: The Solution object is instantiated only once and is reused
by each test case.
if( head==NULL ) return NULL;
RandomListNode* newHead = NULL;
unordered_map< RandomListNode*, RandomListNode* > occur;
dfs( newHead, head, occur );
return newHead;
}
void dfs( RandomListNode*&cur, RandomListNode* node, unordered_map<
RandomListNode*, RandomListNode* >& occur ){
if( node==NULL ) return;
cur = new RandomListNode( node->label );
if( occur.find(node) == occur.end() ){
occur[node] = cur;
}
if( node->next ){
if( occur.find(node->next)==occur.end() ){
dfs( cur->next, node->next, occur );
}else{
cur->next = occur[node->next];
}
}
if( node->random ){
if( occur.find(node->random)==occur.end() ){
dfs( cur->random, node->random, occur );
}else{
cur->random = occur[node->random];
}
}
}
};
*/
