138_javascript.js

// 给你一个长度为 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：

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

// 输入：head = [[1,1],[2,1]]
// 输出：[[1,1],[2,1]]
// 示例 3：

// 输入：head = [[3,null],[3,0],[3,null]]
// 输出：[[3,null],[3,0],[3,null]]
// 示例 4：

// 输入：head = []
// 输出：[]
// 解释：给定的链表为空（空指针），因此返回 null。

// 提示：

// 0 <= n <= 1000
// -10000 <= Node.val <= 10000
// Node.random 为空（null）或指向链表中的节点。

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

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

// 例  [[7,null],[13,0],[11,4],[10,2],[1,0]]
var copyRandomList = function (head) {
  if (head == null) return head;
  let list = head;
  // 使用map存储
  let map = new Map();
  while (list !== null) {
    map.set(list, new Node(list.val, null, null));
    list = list.next;
  }
  // map 的key 为node  value 为 new Node(list.val, null, null)
  // map: {
  //   {
  //     val: 7,
  //     next: => 13
  //     random: null
  //   }  : {
  //     val: 7,
  //     next: null,
  //     random: null
  //   },
  //   ...
  // }

  list = head;
  while (list !== null) {
    // value 的next 为  下一个 value 的值
    map.get(list).next = map.get(list.next) || null;
    // value 的random 为  下一个 value 的random
    map.get(list).random = map.get(list.random) || null;
    list = list.next;
  }
  return map.get(head);
};

// 2 线性的空间复杂度 看题解
//leetcode-cn.com/problems/copy-list-with-random-pointer/solution/liang-chong-shi-xian-tu-jie-138-fu-zhi-dai-sui-ji-/

var copyRandomList = function (head) {
  if (head == null) return head;
  let list = head;
  // 复制一个节点到原节点后面
  while (list !== null) {
    let node = new Node(list.val, null, null);
    node.next = list.next;
    list.next = node;
    list = node.next;
  }
  list = head;
  // 解决random 链接问题
  while (list !== null) {
    if (list.random !== null) {
      // 链接random
      list.next.random = list.random.next;
    }
    list = list.next.next;
  }

  // 最后分离链表
  list = head;
  let res = new Node(-1, null, null);
  let cur = res;
  while (list != null) {
    cur.next = list.next;
    cur = cur.next;
    list.next = cur.next;
    list = list.next;
  }

  return res.next;
};