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

class RandomListNode {
    label: number
    next: RandomListNode | null
    random: RandomListNode | null
    constructor(label?: number, next?: RandomListNode | null, random?: RandomListNode | null) {
        this.label = (label===undefined ? 0 : label)
        this.next = (next===undefined ? null : next)
        this.random = (random===undefined ? null : random)
    }
}
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pHead RandomListNode类 
 * @return RandomListNode类
 */
export function Clone(pHead: RandomListNode): RandomListNode {
    // write code here
//     const nodeMap = new Map();
//     let p = pHead;
//     while(p) {
//         const newNode = new RandomListNode(p.label);
//         nodeMap.set(p, newNode);
//         p = p.next;
//     }
    
//     p = pHead;
//     let start1 = new RandomListNode(0);
//     let start2 = start1;
//     while(p) {
//         const node = nodeMap.get(p);
//         const nextNode = nodeMap.get(p.next);
//         const randomNode = nodeMap.get(p.random);
//         start1 = node;
//         if(nextNode) {
//             start1.next = nextNode;
//         }
//         if(randomNode) {
//             start1.random = randomNode;
//         }
//         p = p.next;
//         start1 = start1.next;
//     }
//     return nodeMap.get(pHead);
    // =======================================================
    if(!pHead) return null;
    const dummy = new RandomListNode(0);
    dummy.next = pHead;
    while(pHead) {
        const copyNode = new RandomListNode(pHead.label);
        copyNode.next = pHead.next;
        pHead.next = copyNode;
        pHead = pHead.next.next;
    }
    let p2 = dummy.next;
    while(p2) {
        if(p2.random) {
            p2.next.random = p2.random.next;
        }
        p2 = p2.next.next;
    }
    let p3 = dummy.next, randomHead = p3.next;
    while(p3) {
        const cloneNode = p3.next;
        p3.next = p3.next? p3.next.next:null;
        p3 = cloneNode;
    }
    return randomHead;
}