LeetCode - 138. Copy List with Random Pointer

우선 내가 생각한 풀이.

예제 3처럼 동일한 val을 가지는 값이 존재할 수 있어서, 값만으로 해당 node를 찾기는 어렵다.

그래서 생각한 게 우선 linked list를 생성해서 val은 다 동일하게 맞추고, random은 이후에 맞추자!

random을 이후에 맞출 때 어떤 노드를 가리키는지 알기 위해 기존 list의 val을 index값으로 바꾼다.

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (head == NULL)
            return NULL;
        vector<int> vals;
        int ind = 0;
        Node* ori = head;
        while(ori != NULL) {
            vals.push_back(ori->val);
            ori->val = ind;
            ind++;
            ori = ori->next;
        }
        cout << endl;
        Node* copy = new Node(vals[0]);
        Node* prev = copy;
        ind = 1;
        while(ind < vals.size()) {
            Node *tmp = new Node(vals[ind]);
            prev->next = tmp;
            ind++;
            prev = tmp;
        }
        ori = head;
        Node* it = copy;
        while(it != NULL) {
            if (ori->random != NULL) {
                Node *tar = copy;
                int count = 0;
                for (int i = 0; i < ori->random->val; i++) {
                    tar = tar->next;
                }
                it->random = tar;
            }
            it = it->next;
            ori = ori->next;
        }
        return copy;
    }
};

뭔가 약간 노가다처럼 됐는데..

일단 vector<vals>에 기존 value들 저장하고, 기존 linked list의 val을 모두 index값으로 설정.(순서대로 0, 1, 2, 3...)

그리고 새로운 linked list를 만들어서 val만 먼저 저장.

이후 while문을 돌면서 기존 linked list에서 random 포인터가 NULL이 아닐 경우, 그 index만큼 새로 생성된 list를 순회해서 그 해당되는 node를 찾음.

 

그리고 다른 방법은 생각이 안 나서 풀이를 찾아봤다.

해시맵을 사용해서 Node끼리 연결할 수가 있었다!

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(!head) return nullptr;

        unordered_map<Node*, Node*> old_to_new;

        Node* curr = head;
        while (curr) {
            old_to_new[curr] = new Node(curr->val);
            curr = curr->next;
        }
        curr = head;
        while(curr) {
            old_to_new[curr]->next = old_to_new[curr->next];
            old_to_new[curr]->random = old_to_new[curr->random];
            curr = curr->next;
        }

        return old_to_new[head];
    }
};

해시맵을 쓸 생각은 전혀 못 했다..

Runtime은 똑같이 나왔다.

 

생각보다 조금 어려웠다.

Key Idea

해당되는 Node 찾기->해시맵