Re: [閒聊] 每日LeetCode

[yam276 (史萊哲林的優等生)]

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
→ Rushia: 大師