/**
* 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) {
//每一個節點指向其複制連結清單相應的節點,進而可以高速定位該節點
if(!head)return NULL;
RandomListNode *p,*q;
p=head;
while(p){
q=new RandomListNode(p->label);
q->next=p->next;
p->next=q;
p=q->next;
}
p=head;
while(p){
q=p->next;
if(p->random)
q->random=p->random->next;
p=q->next;
}
p=head;
RandomListNode*head2=p->next;
q=head2;
while(p){
p->next=q->next;
p=p->next;
if(p){
q->next=p->next;
q=q->next;
}
}
return head2;
}
};
Clone Graph
:
類似的,對于圖的複制,必須找到一種能夠對新圖中節點進行映射,能高速定位新節點的位址,進而使新節點指向新節點。這裡採用map映射。考慮到圖節點的label可能反複(本題不反複),而節點位址不反複,是以以新舊節點為鍵值對。
/**
* Definition for undirected graph.
* struct UndirectedGraphNode {
* int label;
* vector<UndirectedGraphNode *> neighbors;
* UndirectedGraphNode(int x) : label(x) {};
* };
*/
class Solution {
public:
map<UndirectedGraphNode*,UndirectedGraphNode*>mp;
map<UndirectedGraphNode*,UndirectedGraphNode*>::iterator bg;
UndirectedGraphNode* dfs(UndirectedGraphNode*p){
if(!p)return NULL;
if((bg=mp.find(p))!=mp.end())
return bg->second;
UndirectedGraphNode *q;
mp[p]=q=new UndirectedGraphNode(p->label);
for(int i=0,m=p->neighbors.size();i<m;++i){
q->neighbors.push_back(dfs(p->neighbors[i]));
}
return q;
}
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
if(!node)return NULL;
dfs(node);
return mp[node];
}
};