LeetCode 138. Copy List with Random Pointer

本题抽象一下就是如何deep copy图的问题。由于random指针的存在，导致我们按顺序copy的时候，copy的random指针指向的node可能还没有生成。如何解决这个问题是本题的关键。

Recursive

如果递归来做，上述问题很好解决，没有生成的节点递归生成即可。

但是我们需要用一个hashtable来记录原节点与对应copy节点的映射关系，这是因为当前需要copy的节点很可能在之前已经被创建好了。这时我们只要返回已经创建好的节点的指针即可。

class Solution {
public:
    unordered_map<Node *,Node *> m; // original node -> corresponding copied node

    Node* copyRandomList(Node* head) {
        if (head==NULL) return NULL;
        if (m.count(head)) return m[head];
        Node *copy=new Node(head->val,NULL,NULL);
        m[head] = copy;
        copy->next = copyRandomList(head->next);
        copy->random = copyRandomList(head->random);
        return copy;
    }
};

时间复杂度 O(n) 空间复杂度 O(n)

Iterative (Hashtable)

Iterative with O(1) Space