題目：
輸入一個(gè)復(fù)雜鏈表（每個(gè)節(jié)點(diǎn)中有節(jié)點(diǎn)值，以及兩個(gè)指針，一個(gè)指向下一個(gè)節(jié)點(diǎn)，另一個(gè)特殊指針random指向一個(gè)隨機(jī)節(jié)點(diǎn)），請(qǐng)對(duì)此鏈表進(jìn)行深拷貝，并返回拷貝后的頭結(jié)點(diǎn)。（注意，輸出結(jié)果中請(qǐng)不要返回參數(shù)中的節(jié)點(diǎn)引用，否則判題程序會(huì)直接返回空）
第一種方法
思路：
- （1）將鏈表中的節(jié)點(diǎn)用列表存儲(chǔ)
- （2）然后遍歷查找每個(gè)節(jié)點(diǎn)中random指向列表中的哪一個(gè)節(jié)點(diǎn)對(duì)象，并按照列表順序存儲(chǔ)節(jié)點(diǎn)random指向的節(jié)點(diǎn)對(duì)象的下標(biāo)。
- （3）創(chuàng)建新節(jié)點(diǎn)列表
- （4）將新節(jié)點(diǎn)中的next和random進(jìn)行鏈接。
1587908166698.png
代碼：
import java.util.ArrayList;
public class Solution1 {
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
public ArrayList<RandomListNode> toArray(RandomListNode pHead){
if(pHead==null){
return null;
}
ArrayList<RandomListNode> result=new ArrayList<RandomListNode>();
RandomListNode key=pHead;
while(key!=null){
result.add(key);
key=key.next;
}
return result;
}
public int getRandomIndex(ArrayList<RandomListNode> oldNode,RandomListNode key){
for(int i=0;i<oldNode.size();i++){
if(oldNode.get(i).equals(key)){
return i;
}
}
return -1;
}
public int[] getRandomList(ArrayList<RandomListNode> oldNode){
int [] result=new int[oldNode.size()];
for(int i=0;i<oldNode.size();i++){
result[i]=this.getRandomIndex(oldNode,oldNode.get(i).random);
System.out.println(result[i]);
}
return result;
}
public RandomListNode copyNode(RandomListNode old){
return new RandomListNode(old.label);
}
public ArrayList<RandomListNode> getNewList(ArrayList<RandomListNode> oldNode){
ArrayList<RandomListNode> newNode=new ArrayList<>();
for(int i=0;i<oldNode.size();i++){
newNode.add(this.copyNode(oldNode.get(i)));
}
return newNode;
}
public RandomListNode getNewLink(ArrayList<RandomListNode> newNode,int [] randomList){
RandomListNode root=newNode.get(0);
RandomListNode key=root;
for(int i=1;i<newNode.size();i++){
key.next=newNode.get(i);
key=key.next;
}
for(int i=0;i<randomList.length;i++){
if(randomList[i]!=-1){
newNode.get(i).random=newNode.get(randomList[i]);
}
}
return root;
}
public RandomListNode Clone(RandomListNode pHead)
{
//第1步：將原始鏈表數(shù)組化 時(shí)間復(fù)雜度（n）,空間復(fù)雜度（n）
ArrayList<RandomListNode> oldNode=this.toArray(pHead);
if(oldNode==null){
return null;
}
//第2步：遍歷查詢r(jià)andom所指向的node 時(shí)間復(fù)雜度（n^2）,空間復(fù)雜度（0）
int [] randomList=this.getRandomList(oldNode);
//第3步：根據(jù)數(shù)組重新創(chuàng)建一個(gè)新Node數(shù)組，next和random都為null 時(shí)間復(fù)雜度（n）,空間復(fù)雜度（n）
ArrayList<RandomListNode> newNode=this.getNewList(oldNode);
//第4步:鏈接鏈表 時(shí)間復(fù)雜度（n）,空間復(fù)雜度（0）
RandomListNode newRoot=this.getNewLink(newNode,randomList);
return newRoot;
}
public RandomListNode create(){
RandomListNode r1=new RandomListNode(1);
RandomListNode r2=new RandomListNode(2);
RandomListNode r3=new RandomListNode(3);
RandomListNode r4=new RandomListNode(4);
RandomListNode r5=new RandomListNode(5);
RandomListNode r6=new RandomListNode(6);
RandomListNode r7=new RandomListNode(7);
RandomListNode r8=new RandomListNode(8);
r1.next=r2;
r2.next=r3;
r3.next=r4;
r4.next=r5;
r5.next=r6;
r6.next=r7;
r7.next=r8;
r1.random=r3;
r2.random=r4;
r3.random=r5;
r4.random=r6;
r5.random=r7;
r6.random=r8;
r7.random=r1;
r8.random=r2;
return r1;
}
public static void main(String[] args) {
Solution1 s=new Solution1();
RandomListNode root=s.create();
s.Clone(root);
}
}
算法分析：
該方法最復(fù)雜的地方就是尋找random所指向的節(jié)點(diǎn)。
時(shí)間復(fù)雜度O(n^2),空間復(fù)雜度O(n)
代碼運(yùn)行：
運(yùn)行時(shí)間：24ms
占用內(nèi)存：9656k
第二種方法
這個(gè)題目最大的難點(diǎn)在于random引用如何便捷正確的指向?qū)?yīng)的新節(jié)點(diǎn)。
本方法思路：
（1）依次創(chuàng)建新的節(jié)點(diǎn)插入到對(duì)應(yīng)的舊節(jié)點(diǎn)之后
（2）此時(shí)新節(jié)點(diǎn)的random就在舊節(jié)點(diǎn)的random后面，根據(jù)這一規(guī)律，對(duì)新節(jié)點(diǎn)的random進(jìn)行賦值。
-
（3）將組合鏈表中舊節(jié)點(diǎn)刪除，可以借助一個(gè)額外節(jié)點(diǎn)作為暫時(shí)的根節(jié)點(diǎn)。
1587969275319.png
代碼：
public class Solution2 {
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
public void insertNewNodeInLink(RandomListNode pHead){
RandomListNode p=pHead;
while(p!=null){
RandomListNode q=new RandomListNode(p.label);
q.next=p.next;
p.next=q;
p=q.next;
}
}
public void replaceRandom(RandomListNode pHead){
RandomListNode t=pHead;
while(t!=null){
RandomListNode q=t.next;
if(t.random!=null)
q.random=t.random.next;
t=q.next;
}
}
public RandomListNode getNewLink(RandomListNode pHead){
RandomListNode s=new RandomListNode(0);
RandomListNode s1=s;
while(pHead!=null){
RandomListNode q=pHead.next;
pHead.next=q.next;
q.next=s.next;
s.next=q;
s=s.next;
pHead=pHead.next;
}
return s1.next;
}
public RandomListNode Clone(RandomListNode pHead)
{
//第一步：遍歷創(chuàng)建新的復(fù)制節(jié)點(diǎn)，并將其插入到舊鏈表中被復(fù)制節(jié)點(diǎn)之后 時(shí)間復(fù)雜度（n）,空間復(fù)雜度（0）
this.insertNewNodeInLink(pHead);
//第二步：因?yàn)樾鹿?jié)點(diǎn)就在舊節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)，因此random所指的舊節(jié)點(diǎn)向下移一個(gè)，就能夠指向新節(jié)點(diǎn) 時(shí)間復(fù)雜度（n）,空間復(fù)雜度（0）
this.replaceRandom(pHead);
//第三步：將新節(jié)點(diǎn)串聯(lián)成新的鏈表 時(shí)間復(fù)雜度（n）,空間復(fù)雜度（0）
RandomListNode newroot = this.getNewLink(pHead);
return newroot;
}
public RandomListNode create(){
RandomListNode r1=new RandomListNode(1);
RandomListNode r2=new RandomListNode(2);
RandomListNode r3=new RandomListNode(3);
RandomListNode r4=new RandomListNode(4);
RandomListNode r5=new RandomListNode(5);
RandomListNode r6=new RandomListNode(6);
RandomListNode r7=new RandomListNode(7);
RandomListNode r8=new RandomListNode(8);
r1.next=r2;
r2.next=r3;
r3.next=r4;
r4.next=r5;
r5.next=r6;
r6.next=r7;
r7.next=r8;
r1.random=r3;
r2.random=r4;
r3.random=r5;
r4.random=r6;
r5.random=r7;
r6.random=r8;
r7.random=r1;
r8.random=r2;
return r1;
}
public static void main(String[] args) {
Solution2 s=new Solution2();
RandomListNode root=s.create();
RandomListNode t=s.Clone(root);
while(t!=null){
System.out.println(t.label);
t=t.next;
}
}
}
算法分析
空間復(fù)雜度：O(0)
時(shí)間復(fù)雜度：O(n)
運(yùn)行代碼：
運(yùn)行時(shí)間：19ms
占用內(nèi)存：9428k
