题目
给你一个长度为 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 作为传入参数。
输出：head = new Node(val, next, random )输入：[[7,null],[13,0],[11,4],[10,2],[1,0]] function Node(val, next, random) { this.val = val; this.next = next; this.random = random; };题解思路
这题其实就是想复制一个链表构造，给你一个链表的头，因为每个节点都有自身的val，指向下一个节点的next和一个随机指针random，依据next就能顺着链表的头画出整个链表的构造，找到每个节点的随机指针和它自身的next指针。本体要害是不仅要复制节点上的值，这个值十分好拿，相似node.val就能拿到，而后递归或者循环下一次（下一次就是从它的next节点开始复制），拿到所有的val组成一个数组，那么要害是还要复制它的指针，留神，是援用类型，必须明确指向原先指针所指向的那个栈地址。那么，咱们能够把所有节点先遍历进去，存在具备映射关系的Map数据格式中，下次能够不便的拿到原数据，第一次遍历有两个目标：new一个新的Node类，把val复制过去；深拷贝一份原来的节点到map中，用于下次拷贝指针地址。第二遍历就是找到原先指针指向的node，并把复制后的node的next指向map中复制的雷同node，怎么判断雷同呢？就是通过map的key啦。存的时候，就把原先复制前的node当成key，就惟一了。
代码实现
/** * // Definition for a Node. * function Node(val, next, random) { * this.val = val; * this.next = next; * this.random = random; * }; *//** * @param {Node} head * @return {Node} */var copyRandomList = function(head) { if (!head) return null; // head为空的时候，返回空 const map = new Map(); // 创立一个Map数据结构 let node = head; // 第一次遍历，拿值，通过把node当成key复制一个新new的Node对象，有了值，下次再复制random指针和next指针 while(node) { map.set(node, new Node(node.val)); // 复制一个node，key就是target，value就是source。先 复制值 node = node.next; // 一个节点一个节点往下找 } node = head; // node从新赋值，进行第二次遍历，复制指针 while (node) { const n = map.get(node); // 拿到以后node对应的复制后的node。因为要给他复制指针信息了。 n.next = node.next ? map.get(node.next) : null; // 判断原先的node上有没有next指针，有的话，让复制后的node的next指针指向原先指针向的node（这里是复制后的node），通过key对应起来 n.random = node.random ? map.get(node.random) : null; // 同理 node = node.next; } return map.get(head); // 返回的是复制后的链表哦。通过key查找};