138. Copy List with Random Point

给你一个长度为 n 的链表，每个节点包含一个 next 指针和一个random 指针，random 指针可以指向链表中的任何节点或空节点。构造这个链表的深拷贝，新链表由 n 个全新节点组成，复制链表的指针不应指向原链表中的节点。

遍历

用map留存克隆过的数组，然后进行遍历

• 时间复杂度O(n)，空间复杂度O(1)
• Runtime: 84 ms, faster than 47.37%
• Memory Usage: 40.7 MB, less than 19.00%

/**
 * // Definition for a Node.
 * function Node(val, next, random) {
 *    this.val = val;
 *    this.next = next;
 *    this.random = random;
 * };
 */

/**
 * @param {Node} head
 * @return {Node}
 */

var map = new Map()
var copyRandomList = function(head) {
    if(head === null) return null
    
    let copy = new Node(head.val)
    map.set(head, copy)
    let p = head
    
    while(head !== null) {
        copy.next = getCloneNode(head.next)
        copy.random = getCloneNode(head.random)
        
        copy = copy.next
        head = head.next
    }
    return map.get(p)
};

var getCloneNode = function(node) {
    if(node === null) return null
    if(!map.has(node)) {
        map.set(node, new Node(node.val, null, null))
    }
    return map.get(node)
}