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

1.在每个节点插入复制的节点

2.对复制节点的random进行赋值

3.对链表进行拆分

function RandomListNode(x){
    this.label = x;
    this.next = null;
    this.random = null;
}
function Clone(pHead)
{
    // write code here
    if(pHead == null) {return pHead}
    var rtemp = pHead
    var ctemp = pHead
    while(pHead) {
        var clone = new RandomListNode(pHead.label)
        clone.next = pHead.next
        pHead.next = clone
        pHead = clone.next
    }
    while(rtemp) {
        var rclone = rtemp.next
        rclone.random = rtemp.random?rtemp.random.next: null
        if(rclone.next!=null) {rtemp = rclone.next} else break
    }
    var oldh = ctemp
    var newh = ctemp.next
    var oldt = ctemp
    var newt = ctemp.next
    while(newt.next) {
        oldt.next = newt.next
        var temp = oldt.next
        newt.next = temp.next
        oldt = oldt.next
        newt = newt.next
    }
    return newh
}
module.exports = {
    Clone : Clone
};