国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > php框架 > 框架设计 > leetcode || 138、Copy List with Random Pointer

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]; } };


生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生