leetcode || 138、Copy List with Random Pointer
來源：程序員人生 發布時間：2015-07-30 14:51:27 閱讀次數：3539次
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];
}
};
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
