復雜鏈表的復制
題目描述
輸入一個復雜鏈表（每個節(jié)點中有節(jié)點值叭披，以及兩個指針究反，一個指向下一個節(jié)點，另一個特殊指針指向任意一個節(jié)點）暴匠，返回結(jié)果為復制后復雜鏈表的head。（注意傻粘，輸出結(jié)果中請不要返回參數(shù)中的節(jié)點引用每窖，否則判題程序會直接返回空）
思路一
- 遞歸思想：把大問題轉(zhuǎn)換為若干小問題。
- 將復雜鏈表分為頭結(jié)點和剩余結(jié)點兩部分弦悉，剩余部分采用遞歸方法窒典。
/*function RandomListNode(x){
this.label = x;
this.next = null;
this.random = null;
}*/
function Clone(pHead)
{
if(pHead == null){
return null
}
//復制頭節(jié)點
let node = new RandomListNode(pHead.label);
node.random = pHead.random;
//遞歸剩余節(jié)點
node.next = Clone(pHead.next);
return node;
}
思路二
-
在舊鏈表中，復制每一個結(jié)點警绩，并將復制的結(jié)點插入該結(jié)點后面崇败。
image -
遍歷鏈表盅称，初始化復制結(jié)點的random指向肩祥。
image 將鏈表拆分為原鏈表和復制所得鏈表。
image
function RandomListNode(x) {
this.label = x;
this.next = null;
this.random = null;
}
function Clone(pHead) {
if (pHead === null) return;
// 對應(yīng)思路二中的第一步：
let currNode = pHead;
while(currNode!==null){
let cloneNode = new RandomListNode(currNode.label);
cloneNode.next = currNode.next;
currNode.next = cloneNode;
currNode = cloneNode.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)思路二中的第三步：
let cloneHead = pHead.next;
currNode = pHead.next;
while(currNode.next){
currNode.next = currNode.next.next;
currNode = currNode.next;
}
return cloneHead;
}
