Leetcode - 138. Copy List with Random Pointer 풀이

문제

링크드리스트가 주어진다. 노드에는 next 포인터와 random 포인터가 있는데, random은 해당 리스트내부의 무작위 노드를 가리킨다. 이 링크드리스트를 복사하여 새로운 링크드 리스트를 만들어라.

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

해결 아이디어

• 노드의 값만 복사하는것은 쉽다. 문제는 random 노드.
• 기존리스트와, 새 리스트에 해당하는 노드포인터와, 순서를 해시테이블에 저장하고. 이를 이용해 새로운 리스트의 각 노드의 ramdom포인터를 구하는 방식이다.
  • 두개의 해시테이블의 key, value순서가 서로 다르다.
• copy->random = idx_new[orig_idx[node->random]]; 저장된 해시테이블에서 순서에 따른 노드를 바로 얻을 수 있다.
• 잘 생각해보면 orig_idx, idx_new 두개의 해시테이블을 만들필요가 없다. 원본리스트와 새 리스트의 같은순서의 노드를 서로 mapping만 시켜놓으면 된다. unordered_map<Node *, Node *> map;
  • 아래 개선된 풀이 참고.

풀이

class Solution {
public:
    Node* copyRandomList(Node* head) {
        unordered_map<Node *, int> orig_idx;
        unordered_map<int, Node *> idx_new;
        
        Node *newhead = new Node(0);
        Node *node = head;
        Node *copy = newhead;
        int idx = 0;
        for (; node; node = node->next, copy = copy->next) {
            copy->next = new Node(node->val);   
            orig_idx[node] = idx;
            idx_new[idx] = copy->next;
            idx++;
        }
        node = head;
        copy = newhead->next;
        for (; node; node = node->next, copy = copy->next) {
            if (node->random)
                copy->random = idx_new[orig_idx[node->random]];
            else
                copy->random = NULL;
        }
            
        return newhead->next;
    }
};

아래는 주어지는 Node 구조체 형태.

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

개선된 풀이

잘 생각해보면 orig_idx, idx_new 두개의 해시테이블을 만들필요가 없다. 원본리스트와 새 리스트의 같은순서의 노드를 서로 mapping만 시켜놓으면 된다. unordered_map<Node *, Node *> map;

class Solution {
public:
    Node *copyRandomList(Node *head) {
        unordered_map<Node *, Node *> map;
        
        Node *new_head = new Node(0);
        Node *gen = new_head;
        Node *n = head;
        int idx = 0;
        for (; n; n = n->next) {
            gen->next = new Node(n->val);
            gen = gen->next;
            map[n] = gen;
            idx++;
        }
        n = head;
        gen = new_head->next;
        for (; n; n = n->next, gen = gen->next) {
            if (n->random)
                gen->random = map[n->random];
            else
                gen->random = NULL;
        }
        return new_head->next;
    }
};