輸入一個復雜鏈表（每個節點中有節點值，以及兩個指標，一個指向下一個節點，另一個特殊指標random指向一個隨機節點），請對此鏈表進行深拷貝，并回傳拷貝后的頭結點，（注意，輸出結果中請不要回傳引數中的節點參考，否則判題程式會直接回傳空）
解題思路
很復雜的一道題，首先第一步：把復制的結點鏈接在原始鏈表的每一個對應結點的后面
把復制的結點的 random 指標指向被復制結點的 random 指標的下一個結點
從舊鏈表拆分出兩個新鏈表
public class Solution {
public RandomListNode Clone(RandomListNode pHead) {
if(pHead == null) {
return null;
}
RandomListNode curNode = pHead;
// 第一步：為每一個結點復制出新結點，并連接在原結點之后
while(curNode != null) {
RandomListNode node = new RandomListNode(curNode.label);
RandomListNode nextNode = curNode.next;
curNode.next = node;
node.next = nextNode;
curNode = nextNode;
}
// 重新指向鏈表表頭
curNode = pHead;
// 第二步：把復制的結點的 random 指標指向被復制結點的 random 指標的下一個結點
while(curNode != null) {
RandomListNode randomNode = curNode.random;
if(randomNode == null) {
curNode.next.random = null;
} else {
curNode.next.random = randomNode.next;
}
curNode = curNode.next.next;
}
// 第三步：拆分鏈表
curNode = pHead;
RandomListNode cloneHead = curNode.next;
RandomListNode cloneNode = curNode.next;
while(curNode != null) {
curNode.next = cloneNode.next;
curNode = cloneNode.next;
if(curNode != null) {
cloneNode.next = curNode.next;
cloneNode = cloneNode.next;
}
}
return cloneHead;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/166811.html
標籤：其他
上一篇：二叉樹中和為某一值的路徑