/**
* 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];
}
};