题目描述
输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针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]; } };
原文链接: https://www.cnblogs.com/wangshaowei/p/13049968.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/391171
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!