给你一个长度为 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 <= 104Node.random为null或指向链表中的节点。
步骤1：问题分析
题目的要求是对一个链表进行“深拷贝”，这个链表的每个节点有两个指针，一个是next指针指向下一个节点，另一个是random指针，它可以指向链表中的任意节点或空节点。我们需要创建一个新的链表，使其每个节点的值和指针指向和原链表一致，但新链表和原链表中的节点不应相互引用（即新链表应完全独立于原链表）。
输入条件：
head: 链表头节点。- 链表的每个节点都包含两个指针
next和random。 - 节点个数
n的范围是 0 <= n <= 1000。 - 节点值的范围是 -10^4 <= Node.val <= 10^4。
random指针可以指向任意节点或为空。
输出条件：
- 返回新复制链表的头节点，确保新链表是深拷贝，且新链表的结构和随机指针指向关系与原链表一致。
边界条件：
- 链表为空：
head为nullptr。 - 链表中只有一个节点，且
random指针为空或指向自己。 - 所有节点的
random指针为空。 random指针形成复杂的指向关系（如循环引用）。
步骤2：解决方案
在该问题中，简单的遍历一次链表并创建新节点不足以满足要求，因为random指针的关系较为复杂。为了有效完成深拷贝，我们可以采用以下算法：
算法思路：
-
遍历原链表并创建新节点（插入法）：
- 我们在每个原节点后面插入一个新节点，使新节点的
val值等于原节点的val。 - 这样，原链表的每个节点
A后会有一个对应的新节点A'，形成结构A -> A' -> B -> B' ...。 - 时间复杂度为 O(n)。
- 我们在每个原节点后面插入一个新节点，使新节点的
-
处理
random指针：- 因为我们插入了新节点，每个新节点的前一个节点就是它的对应原节点。所以可以用
A.random.next的值来直接设置A'.random。 - 这样只需要遍历一次链表就能设置所有
random指针。 - 时间复杂度为 O(n)。
- 因为我们插入了新节点，每个新节点的前一个节点就是它的对应原节点。所以可以用
-
拆分链表：
- 经过前两步的操作，链表形成了原链表和新链表交替的结构。我们再一次遍历链表，将新节点分离出来，形成深拷贝后的链表。
- 时间复杂度为 O(n)。
复杂度分析：
- 时间复杂度：O(n)，其中 n 是链表节点数量，需要遍历链表三次。
- 空间复杂度：O(1)，因为我们没有使用额外的数据结构。
步骤3：代码实现
代码注释：
- 在原链表中，每个节点后插入一个新节点。
- 设置新节点的
random指针，使它指向原链表中对应的random节点后的新节点。 - 拆分链表，构建出独立的深拷贝链表。
步骤4：启发与优化
该算法利用链表节点之间的交替关系来巧妙地避免额外的空间消耗。这种方式在处理复杂指针结构的链表时非常有效。此外，这种方法在构建深拷贝链表时不需要哈希表等数据结构，降低了空间复杂度。
步骤5：实际应用
该算法可以应用于复杂数据结构的深拷贝。例如，在社交网络的好友关系图中，每个用户节点不仅指向好友（next指针），还可能有推荐好友（random指针）。当需要深度复制社交网络的数据时，此算法可以确保原数据结构和复制数据结构完全独立，从而避免不必要的数据关联。此外，这种深拷贝机制广泛用于复制带复杂引用关系的图、树等结构数据。