題目描述
輸入一個(gè)復(fù)雜鏈表（每個(gè)節(jié)點(diǎn)中有節(jié)點(diǎn)值贴妻，以及兩個(gè)指針缴阎，一個(gè)指向下一個(gè)節(jié)點(diǎn)簇抵，另一個(gè)特殊指針random指向一個(gè)隨機(jī)節(jié)點(diǎn)）庆杜，請對此鏈表進(jìn)行深拷貝，并返回拷貝后的頭結(jié)點(diǎn)碟摆。（注意晃财，輸出結(jié)果中請不要返回參數(shù)中的節(jié)點(diǎn)引用，否則判題程序會(huì)直接返回空）
代碼
- 方法一：
- 遞歸思想：把大問題轉(zhuǎn)換為若干小問題典蜕。
- 將復(fù)雜鏈表分為頭結(jié)點(diǎn)和剩余結(jié)點(diǎn)兩部分断盛，剩余部分采用遞歸方法。
function RandomListNode(x){
this.label = x;
this.next = null;
this.random = null;
}
function Clone(pHead)
{
// write code here
if(!pHead){
return null;
}
let node = new RandomListNode(pHead.label);
node.random = pHead.random;
node.next = Clone(pHead.next);
return node;
}
-
方法二：
思路
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 tmp = null;
currNode = pHead;
while (currNode.next !== null) {
tmp = currNode.next;
currNode.next = tmp.next;
currNode = tmp;
}
return pCloneHead; //這一步不明白
}
