138. Copy List with Random Pointer

1.問題

• 一個linked list中每個node除了next之外, 有個random指針會隨機指向list中的任一node, 回傳這個list的deep copy

2.想法

• 提問

• function header, parameter

• test input

• 觀察

  • 用map儲存已經複製過的node, 避免重複拷貝, 重複走訪

• 說明想法

• 測試計算複雜度

3.程式碼

/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        unordered_map<RandomListNode *, RandomListNode *> m;
        return getCopyNode(head, m);
    }
private:
    RandomListNode * getCopyNode(RandomListNode *head, unordered_map<RandomListNode*, RandomListNode*>& m) {
        if (!head) {
            return NULL;
        }
        if (m.find(head) != m.end()) {
            return m[head];
        }
        
        RandomListNode * node = new RandomListNode(head->label);
        m[head] = node;
        node->next = getCopyNode(head->next, m);
        node->random = getCopyNode(head->random, m);
        return node;
    }
};