题目描述
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
解:复制一个节点，并用map跟原节点关联起来
/* struct RandomListNode { int label; struct RandomListNode *next, *random; RandomListNode(int x) : label(x), next(NULL), random(NULL) { } }; */ class Solution { public: RandomListNode* Clone(RandomListNode* pHead) { if(pHead==nullptr) { return nullptr; } RandomListNode *p1=pHead; RandomListNode *p2=pHead; map<RandomListNode *,RandomListNode *> node_map; while (p1!=nullptr) { RandomListNode *tmp=new RandomListNode(p1->label); node_map[p1]=tmp; p1=p1->next; } while(p2!=nullptr) { if(p2->next!=nullptr) { node_map[p2]->next=node_map[p2->next]; } else { node_map[p2]->next=nullptr; } node_map[p2]->random=node_map[p2->random]; p2=p2->next; } return node_map[pHead]; } };
原创文章，作者：Maggie-Hunter，如若转载，请注明出处：https://blog.ytso.com/17541.html