题解 | #复杂链表的复制#

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
};