138. 随机链表的复制

解题思路

• 遍历整个链表，将每个节点复制一份，同时以旧节点为键，新节点为值存入 map 中
• 判断当前节点的 random 节点是否存在 map，存在则直接赋值取出来进行更新
• 如果当前节点的 random 不存在 map，则以对应的 random 节点为键，当前节点为值存入 map，因为可能存在多个节点指向同一个 random 节点，所以用 set 存储
• 在遍历过程中，同时检查当前节点是否存在被指向的记录，存在则更新 map 中记录的节点，让其 random 指向当前节点复制后的节点

var copyRandomList = function (head) {
  let weakMap = new WeakMap()
  let newMap = new WeakMap()

  function add(node, current) {
    if (!node) return null
    if (weakMap.has(node)) {
      weakMap.get(node).add(current)
    } else {
      weakMap.set(node, new Set([current]))
    }
  }

  function changePointer(current, target) {
    if (weakMap.has(current)) {
      weakMap.get(current).forEach((node) => {
        node.random = target
      })
      weakMap.delete(current)
    }
  }

  function run(head) {
    if (!head) {
      return head
    }

    let newHead = {}
    let prev = newHead
    let current = head

    while (current) {
      prev.next = { ...current }
      newMap.set(current, prev.next) // 处理被复制过的

      if (newMap.has(current.random)) {
        prev.next.random = newMap.get(current.random)
      } else {
        add(current.random, prev.next) // 处理节点还没有复制的
      }

      changePointer(current, prev.next) // 配合 add() 方法处理没复制过的
      prev = prev.next
      current = current.next
    }

    return newHead.next
  }

  return run(head)
}

更多解题思路可以参考 138 题的解题报告 (opens new window)。

参考

-138. 随机链表的复制 - 力扣（LeetCode） (opens new window)