复制复杂链表

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

时间复杂度O(n)，空间复杂度O(n)

/**
 * // 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) {
  let cacheMap = new Map()  // 缓存记录
  let curNode = head  // 遍历节点
  let root = new Node(null) // 复制根节点
  let copyNode = root  // 复制节点
  while (curNode !== null) {
    if (cacheMap.has(curNode)) {// 如果有缓存则取缓存
      copyNode = copyNode.next = cacheMap.get(curNode)
    } else {
      copyNode = copyNode.next = new Node(curNode.val)
      cacheMap.set(curNode, copyNode) //缓存记录
    }
    //处理随机指向节点
    if (curNode.random) {// 如果有缓存则取缓存
      if (cacheMap.has(curNode.random)) {
        copyNode.random = cacheMap.get(curNode.random)
      } else {
        copyNode.random = new Node(curNode.random.val)
        cacheMap.set(curNode.random, copyNode.random)//缓存记录
      }
    }
    curNode = curNode.next
  }

  return root.next
};

TODO:还有一种空间复杂度O(1)的