復(fù)雜鏈表的復(fù)制
題目描述
輸入一個復(fù)雜鏈表（每個節(jié)點中有節(jié)點值炼邀，以及兩個指針，一個指向下一個節(jié)點凄鼻，另一個特殊指針指向任意一個節(jié)點）随橘，返回結(jié)果為復(fù)制后復(fù)雜鏈表的head喂分。（注意，輸出結(jié)果中請不要返回參數(shù)中的節(jié)點引用机蔗，否則判題程序會直接返回空）
思路一
- 遞歸思想：把大問題轉(zhuǎn)換為若干小問題蒲祈。
- 將復(fù)雜鏈表分為頭結(jié)點和剩余結(jié)點兩部分，剩余部分采用遞歸方法萝嘁。
實現(xiàn)代碼
function RandomListNode(x) {
this.label = x;
this.next = null;
this.random = null;
}
function Clone(pHead) {
if (!pHead) {
return null;
}
// 復(fù)制頭結(jié)點
var node = new RandomListNode(pHead.label);
node.random = pHead.random;
// 遞歸其他節(jié)點
node.next = Clone(pHead.next);
return node;
}
思路二
-
在舊鏈表中梆掸，復(fù)制每一個結(jié)點，并將復(fù)制的結(jié)點插入該結(jié)點后面酿愧。
圖片.png -
遍歷鏈表，初始化復(fù)制結(jié)點的random指向邀泉。
圖片.png 將鏈表拆分為原鏈表和復(fù)制所得鏈表嬉挡。
圖片.png
實現(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;
}
