LeetCode剑指 Offer 35—复杂链表的复制（哈希表/递归）

unordered_map

count函数直接放回的是一个数值，如果存在，那么返回1，反之0；

find返回的是一个iterator， 直接输出iterator是会报错的，要输出的话得取出迭代器的值再输出。

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

#include <unordered_map>
class Solution {
public:
    unordered_map<Node*,Node*> h;
    Node* copyRandomList(Node* head) {
        if(head == NULL)
            return head;
        if(!h.count(head))
        {
            Node* n = new Node(head->val);
            // n->val = head->val;
            h[head] = n;
            n->next = copyRandomList(head->next);
            n->random = copyRandomList(head->random);
        }
        return h[head];
    }
};

本题要求我们对一个特殊的链表进行深拷贝。本题中因为随机指针的存在，当我们拷贝节点时，「当前节点的随机指针指向的节点」可能还没创建，因此我们需要随时根据随机指针创建结点。

我们利用回溯的方式，对于当前节点，我们首先要进行拷贝值，然后我们进行「当前节点的后继节点」和「当前节点的随机指针指向的节点」拷贝（我们检查「当前节点的后继节点」和「当前节点的随机指针指向的节点」的创建情况。如果这两个节点中的任何一个节点的新节点没有被创建，我们都立刻递归地进行创建。），拷贝完成后将创建的新节点的指针返回，即可完成当前节点的两指针的赋值。

我们用哈希表记录每一个节点对应新节点的创建情况。注意一个节点可能被多个其他节点指向，因此我们可能递归地多次尝试拷贝某个节点，为了防止重复拷贝，我们需要首先检查当前节点是否被拷贝过，如果已经拷贝过，我们可以直接从哈希表中取出拷贝后的节点的指针并返回即可。