Re: [閒聊] 每日LeetCode已回收
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;
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.193.249.242 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1693934110.A.2C9.html
※ 編輯: yam276 (123.193.249.242 臺灣), 09/06/2023 01:17:07
→
09/06 14:14,
2年前
, 1F
09/06 14:14, 1F
討論串 (同標題文章)
完整討論串 (本文為第 406 之 719 篇)：