138. Copy List with Random Pointer
deep copy一个有next跟random方向指标的linked list：
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};
Solution:
建立hash map，从head跑两次while
第一次new出新的list赋值val
第二次把next跟random塞进去
如果要不能用stl的方法
改成建立 A -> A' -> B -> B'...最后串起来
取代unordered_map<Node*, Node*>
其他原理一样
Code:
class Solution
{
public:
Node* copyRandomList(Node* head)
{
if(!head)
return m_result;
Node* cur = head;
while(cur)
{
m_node_map[cur] = new Node(cur->val);
cur = cur->next;
}
cur = head;
while(cur)
{
if(cur->next)
m_node_map[cur]->next = m_node_map[cur->next];
if(cur->random)
m_node_map[cur]->random = m_node_map[cur->random];
cur = cur->next;
}
return m_node_map[head];
}
private:
unordered_map<Node*,Node*> m_node_map;
};