今天，小吴教你学会影分身

大家好，我是 拷贝忍者吴吴吴 ，在火影忍者的世界里，有一个备受大家喜欢的忍术--- 多重影分身之术 ，，一次性可以分出上千个影分身，并且分身具备实体意识，所以可以用来做一些你想象中的那些事情，比如让他下楼丢垃圾取外卖等等。

但是，这个忍术的级别属于 A 级，并且被列为禁术，一般人学不来，所以，今天拷贝忍者吴吴吴先教你学会如何复制一个分身，等实际成熟再传授禁术。

怎么样复制一个分身呢？

每个人都是由无数的原子组合，所以先从复制一个原子开始，以复制一个复杂链表为例吧。

一、题目描述

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null 。

示例 1：

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

提示：

• -10000 <= Node.val <= 10000
• Node.random 为空（null）或指向链表中的节点。
• 节点数目不超过 1000 。

二、题目解析

我们依旧用 四步分析法 进行结构化的分析。

• 模拟：模拟题目的运行。
• 规律：尝试总结出题目的一般规律和特点。
• 匹配：找到符合这些特点的数据结构与算法。
• 边界：考虑特殊情况。

1、模拟

对于链表中的每个节点来说，它都有三个特征：

• 值为 val
• 一个指向下一个节点的指针 next
• 一个指向随机节点的指针 random

要想 复制这样一个复杂链表 必须要考虑到这三个特征。

如果没有 random 指针的话，那就是普通的链表，只需要遍历链表，然后每轮创建新节点，同时赋值 val 和调整前驱指针指向当前节点就行。

这题出现了 random 指针，由于它可以指向 null 、前面的节点或者后面的节点， 无法做到在一次遍历的过程中就确定下来，因为如果是 指向后面的节点 ，但后面的节点还没有创建生成，无法确定。

所以，我们需要在 一开始把所有的节点都创建出来 ，避免 random 找不到指向，同时观察上图， 每个节点都通过 random 对应着一个新的节点 ，这种一一对应的关系，符合 哈希表 的特征。

此时的哈希表 以原链表的节点作为键，新创建的节点作为值 。

原链表（Key）中的每个节点都有 next 和 random 指针，而新链表（Value） 没有 next 和 random 指针。

需要通过第二次的遍历过程进行指针指向的调整。

在第二次遍历过程中，以原链表中的节点作为键，查找当前 原节点 的指针指向，然后调整 新节点 的指针指向。

2、规律

无

3、匹配

数据结构为链表，遍历方式使用 while 的方式。

4、边界

• 链表为空

三、动画描述

四、图片描述