题目：
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
第一种方法
思路：
- （1）将链表中的节点用列表存储
- （2）然后遍历查找每个节点中random指向列表中的哪一个节点对象，并按照列表顺序存储节点random指向的节点对象的下标。
- （3）创建新节点列表
- （4）将新节点中的next和random进行链接。
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步：将原始链表数组化 时间复杂度（n）,空间复杂度（n）
ArrayList<RandomListNode> oldNode=this.toArray(pHead);
if(oldNode==null){
return null;
}
//第2步：遍历查询random所指向的node 时间复杂度（n^2）,空间复杂度（0）
int [] randomList=this.getRandomList(oldNode);
//第3步：根据数组重新创建一个新Node数组，next和random都为null 时间复杂度（n）,空间复杂度（n）
ArrayList<RandomListNode> newNode=this.getNewList(oldNode);
//第4步:链接链表 时间复杂度（n）,空间复杂度（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);
}
}
算法分析：
该方法最复杂的地方就是寻找random所指向的节点。
时间复杂度O(n^2),空间复杂度O(n)
代码运行：
运行时间：24ms
占用内存：9656k
第二种方法
这个题目最大的难点在于random引用如何便捷正确的指向对应的新节点。
本方法思路：
（1）依次创建新的节点插入到对应的旧节点之后
（2）此时新节点的random就在旧节点的random后面，根据这一规律，对新节点的random进行赋值。
-
（3）将组合链表中旧节点删除，可以借助一个额外节点作为暂时的根节点。
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)
{
//第一步：遍历创建新的复制节点，并将其插入到旧链表中被复制节点之后 时间复杂度（n）,空间复杂度（0）
this.insertNewNodeInLink(pHead);
//第二步：因为新节点就在旧节点的后一个节点，因此random所指的旧节点向下移一个，就能够指向新节点 时间复杂度（n）,空间复杂度（0）
this.replaceRandom(pHead);
//第三步：将新节点串联成新的链表 时间复杂度（n）,空间复杂度（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;
}
}
}
算法分析
空间复杂度：O(0)
时间复杂度：O(n)
运行代码：
运行时间：19ms
占用内存：9428k
