復(fù)雜鏈表的復(fù)制

題目描述

輸入一個(gè)復(fù)雜鏈表（每個(gè)節(jié)點(diǎn)中有節(jié)點(diǎn)值，以及兩個(gè)指針，一個(gè)指向下一個(gè)節(jié)點(diǎn)，另一個(gè)特殊指針指向任意一個(gè)節(jié)點(diǎn)），返回結(jié)果為復(fù)制后復(fù)雜鏈表的head。（注意，輸出結(jié)果中請不要返回參數(shù)中的節(jié)點(diǎn)引用，否則判題程序會(huì)直接返回空）

思路一

1. 遞歸思想：把大問題轉(zhuǎn)換為若干小問題。
2. 將復(fù)雜鏈表分為頭結(jié)點(diǎn)和剩余結(jié)點(diǎn)兩部分，剩余部分采用遞歸方法。

實(shí)現(xiàn)代碼

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

function Clone(pHead) {
    if (!pHead) {
        return null;
    }
    // 復(fù)制頭結(jié)點(diǎn)
    var node = new RandomListNode(pHead.label);
    node.random = pHead.random;
    // 遞歸其他節(jié)點(diǎn)
    node.next = Clone(pHead.next);
    return node;
}

思路二

1. 在舊鏈表中，復(fù)制每一個(gè)結(jié)點(diǎn)，并將復(fù)制的結(jié)點(diǎn)插入該結(jié)點(diǎn)后面。

   
   
   圖片.png

2. 遍歷鏈表，初始化復(fù)制結(jié)點(diǎn)的random指向。

   
   
   圖片.png

3. 將鏈表拆分為原鏈表和復(fù)制所得鏈表。

圖片.png

實(shí)現(xiàn)代碼

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

function Clone(pHead) {
    if (pHead === null) return;

    // 對應(yīng)思路二中的第一步：
    var currNode = pHead;
    while (currNode !== null) {
        var node = new RandomListNode(currNode.label);
        node.next = currNode.next;
        currNode.next = node;
        currNode = node.next;
    }

    // 對應(yīng)思路二中的第二步：
    currNode = pHead;
    while (currNode !== null && currNode.next !== null) {
        if (currNode.random) {
            currNode.next.random = currNode.random.next;
        }
        currNode = currNode.next.next;
    }

    //拆分，對應(yīng)思路二中的第三步：        
    var pCloneHead = pHead.next;
    var temp = null;
    currNode = pHead;
    while (currNode.next !== null) {
        tmp = currNode.next;
        currNode.next = tmp.next;
        currNode = tmp;
    }
    return pCloneHead;
}