复制带随机指针的链表

[louzhedong]

习题

出处 LeetCode 算法第138题

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。

要求返回这个链表的深度拷贝。

思路

用一个map来保存已访问过的节点

解答

/**
 * @param {RandomListNode} head
 * @return {RandomListNode}
 */
function copyRandomList(head) {
  return copy(head, {});
}

function copy(node, map) {
  if (!node) return node;
  if (map[node.label]) return map[node.label];

  let n = new RandomListNode(node.label);

  map[node.label] = n;

  n.next = copy(node.next, map);
  n.random = copy(node.random, map);

  return n;
}