题目描述
输入一个复杂链表 (每个节点中有节点值, 以及两个指针, 一个指向下一个节点, 另一个特殊指针指向任意一个节点), 返回结果为复制后复杂链表的 head.(注意, 输出结果中请不要返回参数中的节点引用, 否则判题程序会直接返回空)
- /*
- 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 == NULL){
- return NULL;
- }
- map<RandomListNode*,RandomListNode*>tmpMap;
- RandomListNode* p1 = NULL;
- RandomListNode* p2Head = NULL;
- RandomListNode* tmpHead = pHead;
- if(tmpHead){
- p1 = new RandomListNode(tmpHead->label);
- p2Head = p1;
- tmpMap[tmpHead] = p1;
- tmpHead = tmpHead->next;
- }
- while(tmpHead){
- RandomListNode* tmp = new RandomListNode(tmpHead->label);
- p1->next = tmp;
- p1 = tmp;
- tmpMap[tmpHead] = tmp;
- tmpHead = tmpHead->next;
- }
- tmpHead = pHead;
- map<RandomListNode*,RandomListNode*>::iterator it;
- map<RandomListNode*,RandomListNode*>::iterator it_random;
- while(tmpHead){
- if(tmpHead->random){
- it = tmpMap.find(tmpHead);
- if(it != tmpMap.end()){
- it_random = tmpMap.find(tmpHead->random);
- if(it_random != tmpMap.end()){
- it->second->random = it_random->second;
- }
- }
- }
- tmpHead = tmpHead->next;
- }
- return p2Head;
- }
- };
来源: http://www.bubuko.com/infodetail-2588333.html