leetcode || 138、Copy List with Random Pointer
来源：程序员人生 发布时间：2015-07-30 14:51:27 阅读次数：3019次
problem：
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.
Hide Tags
Hash Table Linked
List
题意：copy1个单链表，单链表的节点多了1个指针，随机指向1个节点或空
thinking：
（1）这道题其实蛮简单，窍门在于hash table的利用。
（2）使用 unordered_map<RandomListNode *, RandomListNode *> record;底层是借助hash table实现的，访问效力高。
这类存储新旧节点指针的方法在图的copy中也用到过，效力奇高！
（3）先遍历链表，将新旧节点指针存入hash table，先不管next指针和random指针。
（4）再遍历hash table，找到旧节点next和random的指向，跟新新节点的next指针和random指针。
注意先调用count（）或find（）判断key值是不是存在
code：
class Solution {
private:
unordered_map<RandomListNode *, RandomListNode *> record;
queue<RandomListNode *> _queue;
public:
RandomListNode *copyRandomList(RandomListNode *head) {
if(head==NULL)
return NULL;
_queue.push(head);
while(!_queue.empty())
{
RandomListNode *tmp=_queue.front();
_queue.pop();
if(tmp->next!=NULL)
_queue.push(tmp->next);
RandomListNode *tmp2= new RandomListNode(tmp->label);
record.insert(make_pair(tmp,tmp2));
}
for(unordered_map<RandomListNode *,RandomListNode *>::iterator it=record.begin();it!=record.end();++it)
{
RandomListNode *tmp3=it->first;
RandomListNode *tmp4=it->second;
if(record.count(tmp3->next)!=0)
tmp4->next=record[tmp3->next];
else
tmp4->next=NULL;
if(record.count(tmp3->random)!=0)
tmp4->random=record[tmp3->random];
else
tmp4->random=NULL;
}
return record[head];
}
};
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
