XingHuiSamaの宝藏之地

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

你的代码只接受原链表的头节点 head 作为传入参数。

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

示例 3：

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

提示：

0 <= n <= 1000
-104 <= Node.val <= 104
Node.random 为 null 或指向链表中的节点。

1. 算法核心思想：空间换时间与地址映射

最大难点在于：在克隆当前节点并试图连接其 random 指针时，目标节点可能尚未被创建。为了打破这种“时空错位”的限制，本解法采用了哈希表（Hash Map）记录节点映射关系的策略。

算法严格遵循了“先实体制造，后关系连线”的解耦思想。哈希表的键（Key）保存原链表节点的内存地址，值（Value）保存对应新创建的克隆节点的内存地址。当所有的物理节点都被 new 出来之后，任意节点的关联指向都可以在 O(1) 的时间内通过查表精准完成。

2. 逻辑拆解

阶段一：节点实例化与建表 利用指针 p 遍历整条原链表。每遇到一个节点，就立刻在堆区申请内存生成一个值相同的新节点（new Node），并将这组“真身与克隆体”的地址映射关系存入 map 中。这一步保证了后续所有的指针连线操作都不会遇到空引用的情况。
阶段二：组装 next 关系游标 first 回到起点。对于每一个原节点，在哈希表中查出它对应的克隆节点 mapfirst。通过严格的 if-else 判定，查出原节点下一步的克隆体并赋值给 mapfirst->next。
阶段三：组装 random 关系逻辑与阶段二完全一致，游标再次回到起点。根据原节点 random 的指向，查出对应的克隆体并赋值给 mapfirst->random，完成了随机指针的复刻。
安全返回：最后直接返回 map[head]。如果传入的 head 为 NULL，C++ 的 unordered_map 针对不存在的键默认返回 NULL，代码因此隐式地安全处理了空链表的边界输入。

class Solution {
public:
    Node* copyRandomList(Node* head) {
        Node* p = head;
        // 声明哈希表，用于存储 <原节点指针, 新节点指针> 的映射关系
        unordered_map<Node*, Node*> map;
        
        // 第一阶段：遍历原链表，在堆内存中创建所有新节点，并建立映射
        while (p != NULL) {
            Node* temp = new Node(p->val);
            map[p] = temp;
            p = p->next;
        }

        // 第二阶段：再次遍历，专门负责连接所有新节点的 next 指针
        Node* first = head;
        while (first != NULL) {
            auto mapfirst = map[first]; // 取出当前节点对应的克隆体
            Node* pre;
            if (first->next == NULL) {
                pre = NULL;
            }
            else {
                pre = map[first->next]; // 查表获取原链表 next 对应的克隆体
            }
            mapfirst->next = pre;
            first = first->next;
        }

        // 第三阶段：第三次遍历，专门负责连接所有新节点的 random 指针
        first = head;
        while (first != NULL) {
            auto mapfirst = map[first];
            Node* pre;
            if (first->random == NULL) {
                pre = NULL;
            }
            else {
                pre = map[first->random]; // 查表获取原链表 random 对应的克隆体
            }
            mapfirst->random = pre;
            first = first->next;
        }

        // 返回原头节点所对应的克隆头节点
        return map[head];
    }
};

3. 复杂度分析

时间复杂度：O(N)。其中 N 为链表的长度。代码对链表进行了三次相互独立的线性遍历，时间总消耗为 3N，依然属于 O(N) 的线性时间复杂度级别。哈希表的存取平均时间复杂度为 O(1)。
空间复杂度：O(N)。算法额外开辟了一个 unordered_map 来存储每个节点的映射关系。由于链表有 N 个节点，哈希表中会存放 N 个键值对，因此额外空间开销与数据规模成正比。