思路

leetcode - 138. 复制带随机指针的链表

July 22, 2021

思路

借助hash表原链表一一映射生成链表节点, 最后遍历组装

function copyRandomList(head: Node | null): Node | null {
  let dummy = new Node()
  const map = new Map()

  let newHead = dummy, iterator = head

  while(iterator) {
    map.set(iterator, new Node(iterator.val))
    iterator = iterator.next
  }

  iterator = head

  while(iterator) {
    iterator = iterator.next
    const cur = map.get(iterator)
    if (cur) {
      cur.next = map.get(iterator.next) || null
      cur.random = map.get(iterator.random) || null
    }
  }

  return newHead.next
};

feiker 少年起而行之