剑指 Offer 35. 复杂链表的复制、深拷贝、哈希表

写前吐槽，希望十月不是 dp 月，今天的每日一题已放弃。

剑指 Offer 35. 复杂链表的复制

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

示例 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。

提示：

• -10000 <= Node.val <= 10000
• Node.random 为空（null）或指向链表中的节点。
• 节点数目不超过 1000 。

注意：本题与主站 138 题相同：https://leetcode-cn.com/problems/copy-list-with-random-pointer/

思路

和 js 用递归手动实现深拷贝是一种思路，使用 weakmap 存储节点，避免重复递归。需要注意的是，这里 val 也不能直接赋值，应该也再递归调用，再判断是不是非对象类型，是的话直接返回。

解答

/**
 * // 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) {
  const map = new WeakMap();
  const deepCopy = (node) => {
    if (typeof node !== "object") return node;
    if (map.has(node)) return map.get(node);
    if (!node) return null;
    const res = {};
    map.set(node, res);
    for (key of Reflect.ownKeys(node)) {
      res[key] = deepCopy(node[key]);
    }
    return res;
  };
  return deepCopy(head);
};