关于javascript:码不停题算法篇复制带随机指针的链表

7次阅读

共计 1796 个字符，预计需要花费 5 分钟才能阅读完成。

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

正文完