剑指offer - 复杂链表的复制 - JavaScript

【复杂链表的复制】【JavaScript解法】

思路

用一个哈希表表示映射关系：键是原节点，值是复制的节点。

整体算法流程是：

• 第一次遍历，复制每个节点和 next 指针，并且保存“原节点-复制节点”的映射关系
• 第二次遍历，通过哈希表获得节点对应的复制节点，更新 random 指针

代码实现

使用 ES6 的Map，可以直接将对象作为键值。

JavaScript 代码实现：

// ac地址：https://www.nowcoder.com/practice/f836b2c43afc4b35ad6adc41ec941dba
// 原文地址：https://xxoo521.com/2020-02-05-link-copy/

// function RandomListNode(x){
//     this.label = x;
//     this.next = null;
//     this.random = null;
// }

function Clone(pHead) {
    if (!pHead || !pHead.next) {
        return pHead;
    }
    const map = new Map();
    let node = pHead;
    const newHead = new RandomListNode(node.label);
    let newNode = newHead;
    map.set(node, newNode);

    while (node.next) {
        newNode.next = new RandomListNode(node.next.label);
        node = node.next;
        newNode = newNode.next;
        map.set(node, newNode);
    }

    newNode = newHead;
    node = pHead;
    while (newNode) {
        newNode.random = map.get(node.random);
        newNode = newNode.next;
        node = node.next;
    }

    return newHead;
}

博客地址：剑指 Offer 题解+代码

收藏 Github ：https://github.com/dongyuanxin/blog