【js刷题--链表】JZ35 复杂链表的复制

不断遍历指向新地址即可，但是有random，
可以用new Node创建新节点，建立映射关系
先检查map中有没有这个节点，有直接放进map中，没有再新创建
方法一

function RandomListNode(x){
    this.label = x;
    this.next = null;
    this.random = null;
}
function Clone(pHead)
{
    // write code here
    const map = new Map();
    const copy = (head)=>{
        if(head == null) return null;
        //如果已经存在，直接map获得即可
        if(map.has(head)) return map.get(head);
        //如果没有，则定义一个新节点，复制head
        const res = new RandomListNode(head.label);
        //如果这里不创建映射关系，会报错，重复创建res
        map.set(head,res);
        //此时，继续往下copy下一个节点，循环的意思，直到head为null
        res.next = copy(head.next);
        res.random = copy(head.random);
        return res;
    }    
    return copy(pHead);
}
module.exports = {
    Clone : Clone
};

方法二

基本思想：先挨个在每个节点之后 复制新的节点，然后再处理新节点的random指针
最后把链表中复制的节点拆分出来

function RandomListNode(x){
    this.label = x;
    this.next = null;
    this.random = null;
}
function Clone(pHead)
{
    // write code here
    if(pHead ===null) return null;
    let pre = pHead,next = pre.next;
    //先在每个节点之后复制一个一模一样的节点
    while(pre){
        pre.next = new RandomListNode(pre.label);
        pre.next.next= next;
        pre = next;
        next = pre?pre.next:null;
    }
    //处理复制后节点的random
    pre = pHead,next = pre.next;
    while(next){
        //复制后节点的random指针：是被复制指针的random指针的下一个节点
        next.random = pre.random?pre.random.next:null;
        pre = next.next;
        next = pre?pre.next:null
    }
    //拆分链表
    const res = pHead.next;
    pre = pHead,next = pre.next;
    while(next){
        pre.next = next.next;
        //此时pre是原链表的下一个节点
        pre = pre.next;
        //此时需要判断现在的pre是否为空,不为空，则指向现在pre.next
        next.next = pre?pre.next:null;
        next = next.next;
    }
    return res
}
module.exports = {
    Clone : Clone
};