给你一个长度为 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：问题分析

题目的要求是对一个链表进行“深拷贝”，这个链表的每个节点有两个指针，一个是next指针指向下一个节点，另一个是random指针，它可以指向链表中的任意节点或空节点。我们需要创建一个新的链表，使其每个节点的值和指针指向和原链表一致，但新链表和原链表中的节点不应相互引用（即新链表应完全独立于原链表）。

输入条件：

• head: 链表头节点。
• 链表的每个节点都包含两个指针next和random。
• 节点个数 n 的范围是 0 <= n <= 1000。
• 节点值的范围是 -10^4 <= Node.val <= 10^4。
• random 指针可以指向任意节点或为空。

输出条件：

• 返回新复制链表的头节点，确保新链表是深拷贝，且新链表的结构和随机指针指向关系与原链表一致。

边界条件：

1. 链表为空：head 为 nullptr。
2. 链表中只有一个节点，且 random 指针为空或指向自己。
3. 所有节点的 random 指针为空。
4. random 指针形成复杂的指向关系（如循环引用）。

步骤2：解决方案

在该问题中，简单的遍历一次链表并创建新节点不足以满足要求，因为random指针的关系较为复杂。为了有效完成深拷贝，我们可以采用以下算法：

算法思路：

1. 遍历原链表并创建新节点（插入法）：

   • 我们在每个原节点后面插入一个新节点，使新节点的 val 值等于原节点的 val。
   • 这样，原链表的每个节点 A 后会有一个对应的新节点 A'，形成结构 A -> A' -> B -> B' ...。
   • 时间复杂度为 O(n)。

2. 处理random指针：

   • 因为我们插入了新节点，每个新节点的前一个节点就是它的对应原节点。所以可以用 A.random.next 的值来直接设置 A'.random。
   • 这样只需要遍历一次链表就能设置所有random指针。
   • 时间复杂度为 O(n)。

3. 拆分链表：

   • 经过前两步的操作，链表形成了原链表和新链表交替的结构。我们再一次遍历链表，将新节点分离出来，形成深拷贝后的链表。
   • 时间复杂度为 O(n)。

复杂度分析：

• 时间复杂度：O(n)，其中 n 是链表节点数量，需要遍历链表三次。
• 空间复杂度：O(1)，因为我们没有使用额外的数据结构。

步骤3：代码实现

代码注释：

1. 在原链表中，每个节点后插入一个新节点。
2. 设置新节点的 random 指针，使它指向原链表中对应的 random 节点后的新节点。
3. 拆分链表，构建出独立的深拷贝链表。

步骤4：启发与优化

该算法利用链表节点之间的交替关系来巧妙地避免额外的空间消耗。这种方式在处理复杂指针结构的链表时非常有效。此外，这种方法在构建深拷贝链表时不需要哈希表等数据结构，降低了空间复杂度。

步骤5：实际应用

该算法可以应用于复杂数据结构的深拷贝。例如，在社交网络的好友关系图中，每个用户节点不仅指向好友（next指针），还可能有推荐好友（random指针）。当需要深度复制社交网络的数据时，此算法可以确保原数据结构和复制数据结构完全独立，从而避免不必要的数据关联。此外，这种深拷贝机制广泛用于复制带复杂引用关系的图、树等结构数据。