复杂链表的复制
复杂链表的复制
http://www.nowcoder.com/questionTerminal/f836b2c43afc4b35ad6adc41ec941dba
递归调用
Map映射
1判断节点是否,是，返回空节点，否则：
2.从字典判断节点是否已建立，是，返回建立的节点，否则建立新节点；并将新节点写入字典；
3便利next节点和random节点；
返回建立的节点；
class Solution {
public:
RandomListNode* f(RandomListNode* pHead,map<RandomListNode*,RandomListNode*>&M)
{
RandomListNode* p=NULL;
if(pHead==NULL)
return p;
auto ret=M.find(pHead);
if(ret!=M.end())
{
return (*ret).second;
}
p=new RandomListNode(pHead->label);
M.insert(pair<RandomListNode*,RandomListNode*>(pHead,p));
p->next=f(pHead->next,M);
p->random=f(pHead->random,M);
return p;
}
RandomListNode* Clone(RandomListNode* pHead)
{
RandomListNode* p=NULL;
map<RandomListNode*,RandomListNode*>M;
p=f(pHead,M);
return p;
}
}; 
上海得物信息集团有限公司公司福利 1194人发布
查看10道真题和解析