leetcode || 138、Copy List with Random Pointer
来源:程序员人生 发布时间:2015-07-30 14:51:27 阅读次数:3008次
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];
}
};
生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠