题解 | #复杂链表的复制#
复杂链表的复制
https://www.nowcoder.com/practice/f836b2c43afc4b35ad6adc41ec941dba
function RandomListNode(x){
this.label = x;
this.next = null;
this.random = null;
}
function Clone(pHead)
{
// write code here
if (pHead === null) return null
const targetCache = []
const copiedCache = []
let currentNode = pHead
const copiedHead = new RandomListNode(pHead.label)
let currentCopiedNode = copiedHead
targetCache.push(currentNode)
copiedCache.push(currentCopiedNode)
while (currentNode.next) {
const cachedNodeIndex = targetCache.indexOf(currentNode.next)
if (cachedNodeIndex === -1) {
currentCopiedNode.next = new RandomListNode(currentNode.next.label)
copiedCache.push(currentCopiedNode.next)
} else {
currentCopiedNode.next = copiedCache[cachedNodeIndex]
}
if (currentNode.random !== null) {
const cachedRandomNodeIndex = targetCache.indexOf(currentNode.random)
if (cachedRandomNodeIndex === -1) {
currentCopiedNode.random = new RandomListNode(currentNode.random.label)
copiedCache.push(currentCopiedNode.random)
} else {
currentCopiedNode.random = copiedCache[cachedRandomNodeIndex]
}
}
currentNode = currentNode.next
currentCopiedNode = currentCopiedNode.next
targetCache.push(currentNode)
}
return copiedHead
}
module.exports = {
Clone : Clone
};