复杂链表的复制
复杂链表的复制
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; } };