剑指offer 35 拷贝复杂链表

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

我用的方法是: 使用哈希记录当前链表是否被拷贝过

/*
// 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 NULL;

        Node *p = head, *newp,*temp;

        map<Node*, Node*> Hash;
        Node* newhead = new Node(head->val);
        p = head->next;
        newp = newhead;
        Hash.insert(pair<Node*, Node*>(head,newhead));
        while(p)
        {
            auto check = Hash.find(p);
            //hash表中没存next
            if(check == Hash.end())
            {
                temp = new Node(p->val);
                newp->next = temp;
                Hash.insert(pair<Node*, Node*>(p, newp->next));
            }
            else{
                newp->next = check->second;
            }
            
            if(p->random)
            {
                check =Hash.find(p->random);
                //hash表没有存random
                if(check == Hash.end())
                {
                    temp = new Node(p->random->val);
                    newp->next->random = temp;
                    Hash.insert(pair<Node*, Node*>(p->random, newp->next->random));
                }
                else{
                    newp->next->random = check->second;
                }
            }
            
            newp = newp->next;
            
            p = p->next;
            
        }
        
        if(head->random)
        {
            newhead->random = (Hash.find(head->random))->second;
        }

        return newhead;

        
    }
};

时间复杂度: N
空间复杂度: N(额外空间存储哈希)

另外一种方法是: 将新链表逐个插入到老链表中, 形成1-> 1'-> 2-> 2'-> 3-> 3'. 后面就不用说了吧?
一定不能忘了实现