qycl50224#leetcode#138. 复制带随机指针的链表1

# 138. 复制带随机指针的链表 难度：`medium` 题目： 给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。 要求返回这个链表的 **深拷贝**。 我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 `[val, random_index]` 表示： `val`：一个表示 `Node.val` 的整数。 `random_index`：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。 **示例 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]] **示例 4：** > 输入：head = [] > 输出：[] > 解释：给定的链表为空（空指针），因此返回 null。 **提示：** -10000 <= Node.val <= 10000 Node.random 为空（null）或指向链表中的节点。 节点数目不超过 1000 。 ### 思路：直接法 - 第一遍遍历给定链表，创建一个相同val**拷贝链表** - 用一个哈希表把给定链表的每个节点和他的index对应，便于之后找random对应的节点的index - 用另一个哈希表把index和对应的拷贝节点联系，这是为了把拷贝节点的