力扣138. 随机链表的复制

回溯

• 思路：
  • 因为是随机的链接，节点可能创建了也可能没被创建，可以使用一个哈希表来缓存节点及其克隆节点；
  • 利用回溯的方式，对每个节点进行拷贝：
    • 当前节点的拷贝；
    • 当前节点 next 节点的拷贝；
    • 当前节点 random 节点的拷贝；（这个节点可能已经被创建、也可能还没创建）
  • 拷贝完成，返回其克隆节点即可；

/*
// 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 (nullptr == head) {
            return nullptr;
        }

        if (!cachedNode.count(head)) {
            Node* headNew = new Node(head->val);
            cachedNode[head] = headNew;
            headNew->next = copyRandomList(head->next);
            headNew->random = copyRandomList(head->random);
        }

        return cachedNode[head];
    }

private:
    std::unordered_map<Node*, Node*> cachedNode;
};