复杂链表的复制

思路——一步一步做

第1步：先不管random,按照普通链表复制

第2步：从头开始，处理random的复制

代码

function RandomListNode(x){
    this.label = x;
    this.next = null;
    this.random = null;
}
function Clone(pHead)
{
    // write code here
    // 第1步：先复制next。顺便把复制过的节点做记录
    var pre1 = []; // 记录被复制过的节点
    var pre2 = []; // 记录复制后的节点，与pre1一一对应
    var copyed = clone(pHead, pre1, pre2);
    // 第2步：再复制random
    for(var i=0;i<pre1.length;i++){
        // 如果指向的是我pre里记录过的节点
        var index = pre1.indexOf(pre1[i].random);
        pre2[i].random = index ==-1 ? clone(pre1[i].random) : pre2[index];
    }
    return copyed;
}
// 辅助函数，复制链表
function clone(node, pre1, pre2){
    if(node == null){
        return null;
    }
    var copyed = new RandomListNode(node.label);
    if(pre1 !== undefined && pre2 !== undefined){
        pre1.push(node);
        pre2.push(copyed);
    }
    copyed.next = clone(node.next, pre1, pre2);
    return copyed;
}