e*******s
发帖数: 1979 | 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];
}
}
}
};
*/ | e*******s
发帖数: 1979 | 2 这么快就沉了。。
up
【在 e*******s 的大作中提到】
: 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;
|
|
