【算法】复制带随机指针的链表

题目

给你一个长度为 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 2	输入：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查找
};