Copy List with Random Pointer

Description

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

The Linked List is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

• val: an integer representing Node.val
• random_index: the index of the node (range from 0 to n-1) where random pointer points to, or null if it does not point to any node.

 

Example 1:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Example 3:

Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

Example 4:

Input: head = []
Output: []
Explanation: Given linked list is empty (null pointer), so return null.

 

Constraints:

• -10000 <= Node.val <= 10000
• Node.random is null or pointing to a node in the linked list.
• Number of Nodes will not exceed 1000.

Solution(javascript)

/** 记下每个节点对应 radom 节点的位置
 * @param {Node} head
 * @return {Node}
 */
// const copyRandomList = function (head) {
//   const copy = (node) => {
//     if (node) {
//       return new Node(node.val, null, null)
//     }
//     return null
//   }
//   const nodeMap = new Map()
//   let current = head
//   let index = 0
//   while (current) {
//     nodeMap.set(current, index)
//     index += 1
//     current = current.next
//   }
//   const randomMap = []
//   const copyNodeMap = []
//   current = head
//   while (current) {
//     copyNodeMap.push(copy(current))
//     const randomNode = nodeMap.get(current).random
//     if (randomNode) {
//       randomMap.push(nodeMap.get(randomNode))
//     } else {
//       randomMap.push(null)
//     }
//     current = current.next
//   }
//   copyNodeMap.forEach((node, index) => { // eslint-disable-line
//     node.next = copyNodeMap[index + 1] || null
//     node.random = randomMap[index] === null ? null : copyNodeMap[randomMap[index]]
//   })
//   return copyNodeMap[0] || null
// }


/** 其实我们不需要具体的位置信息，我只要相对的位置信息就行了
 * @param {Node} head
 * @return {Node}
 */
const copyRandomList = function (head) {
  const copy = (node) => {
    if (node) {
      return new Node(node.val, null, null)
    }
    return null
  }
  const nodeMap = new Map()
  let current = head
  while (current) {
    nodeMap.set(current, copy(current))
    current = current.next
  }
  current = head
  while (current) {
    nodeMap.get(current).next = nodeMap.get(current.next) || null
    nodeMap.get(current).random = nodeMap.get(current.random) || null
    current = current.next
  }
  return nodeMap.get(head) || null
}