leetcode || 138、Copy List with Random Pointer
來源：程序員人生 發(fā)布時(shí)間：2015-07-30 14:51:27 閱讀次數(shù)：3557次
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個(gè)單鏈表，單鏈表的節(jié)點(diǎn)多了1個(gè)指針，隨機(jī)指向1個(gè)節(jié)點(diǎn)或空
thinking：
（1）這道題其實(shí)蠻簡單，竅門在于hash table的利用。
（2）使用 unordered_map<RandomListNode *, RandomListNode *> record;底層是借助hash table實(shí)現(xiàn)的，訪問效力高。
這類存儲新舊節(jié)點(diǎn)指針的方法在圖的copy中也用到過，效力奇高！
（3）先遍歷鏈表，將新舊節(jié)點(diǎn)指針存入hash table，先不管next指針和random指針。
（4）再遍歷hash table，找到舊節(jié)點(diǎn)next和random的指向，跟新新節(jié)點(diǎn)的next指針和random指針。
注意先調(diào)用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];
}
};
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈
