[LinkedList][Medium] 138. Copy List with Random Pointer

Copy List with Random Pointer - LeetCode

 

list가 주어지고 random 포인터가 랜덤하게 다른 노드를 가리키고 있을 때, 

이 list을 deep copy 하라.

 

약간 난해한 문제. 

우선 직관적으로 해 보면, 

먼저 메모리를 할당해서 기본 list를 copy를 한다.

다음으로 random 포인터의 위치를 index를 파악한다. 

그리고 이 data를 이용해 새로 만든 리스트에서 random의 대상이 되는 노드를 찾아 연결한다. 

 

시간 효율이 좋지 않을 것이 자명하다. 

 

일단 코드 ..

Node* copyRandomList(Node* head) 
{
    Node* newHead = nullptr;
    Node* prev = nullptr;
    Node* node = head;
    Node* newNode = nullptr;

    // Copy 
    while (node != nullptr)
    {
        newNode = new Node(node->val);

        if (newHead == nullptr)
            newHead = newNode;

        if (prev != nullptr)
            prev->next = newNode;

        prev = newNode;
        node = node->next;
    }

    // Store index of random.
    vector<int> vBuff;
    node = head;
    while (node != nullptr)
    {
        vBuff.push_back(-1);
        if (node->random != nullptr)
        {	
            Node* inNode = head;
            for (int k = 0; ; ++k)
            {
                if (inNode == nullptr)	break;
                if (inNode == node->random)
                {
                    vBuff[vBuff.size()-1] = k;
                    break;
                }
                inNode = inNode->next;
            }
        }
        // cout << vBuff[vBuff.size()-1] << endl;
        node = node->next;
    }


    // Link random of newNodes.
    node = newHead;
    int idx = 0;
    while (node != nullptr)
    {
        if (vBuff[idx] < 0)
            node->random = nullptr;
        else
        {
            Node* inNode = newHead;
            for (int k = 0; k < vBuff[idx]; ++k)
                inNode = inNode->next;
            node->random = inNode;
        }
        node = node->next;
        idx++;
    }
    return newHead;
}

 

결과

 

 

추가 버퍼를 어차피 쓴다면 더 좋은 방법은?

 

기존 node에 해당하는 복사 node를 만든다. 

이것들은 hash로 연결한다. 

그러면, next 와 random을 O(1)에 찾을 수 있게 된다. !

 

 

코드 

Node* copyRandomList(Node* head) 
{
    if(head == nullptr) return nullptr;

    unordered_map<Node*, Node*> mBuff;
    Node* node = head;
    while(node != nullptr)
    {
        mBuff[node] = new Node(node->val);
        node = node->next;
    }

    Node* copyHead = mBuff[head];
    Node* prev = nullptr;
    node = head;
    while(node != nullptr)
    {
        Node* newNode = mBuff[node];
        newNode->next = mBuff[node->next];
        newNode->random = mBuff[node->random];

        if(prev != nullptr)
            prev->next = newNode;
        node = node->next;
    }
    return copyHead;
}

속도는 물론이고, 코드가 훨씬 간단해 졌다.

 

 

 

결과