力扣HOT100（42）链表-随机链表的复制

方法一：回溯 + 哈希表（面试首选，好理解、不易错）

1. 核心思路（一句话讲透）

用一个哈希表，存「原节点 → 新节点」的一一对应关系。 这样不管什么时候，只要你需要找某个原节点对应的新节点，直接查哈希表就行，完美解决 “random 指向的节点还没创建” 的问题。

2. 完整解题步骤

1. 创建哈希表：unordered_map<Node*, Node*> cachedNode，key 是原节点，value 是对应的新节点
2. 递归终止条件：如果当前节点是nullptr，直接返回nullptr
3. 检查是否已复制：如果当前节点已经在哈希表中，说明已经复制过了，直接返回对应的新节点（防止重复复制）
4. 创建新节点：复制当前节点的值，存入哈希表
5. 递归复制指针：
   • 递归复制当前节点的next节点，赋值给新节点的next
   • 递归复制当前节点的random节点，赋值给新节点的random
6. 返回新节点

/* // 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: unordered_map<Node*,Node*> cachedNode; Node* copyRandomList(Node* head) { if(head == nullptr){ 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]; } };