题目
解法一
我们先把所有的节点复制下来,然后将源节点存在一个arraylist里面,目的链表存在一个arraylist里面,然后遍历一遍原节点的arraylist找到它的每个节点的random对应的index,在用这个index来找到dst里面的节点的值。
/*
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
*/
import java.util.*;
public class Solution {
public RandomListNode Clone(RandomListNode pHead) {
if(pHead==null)return null;
ArrayList<RandomListNode> src=new ArrayList<>();
ArrayList<RandomListNode> dst=new ArrayList<>();
while(pHead!=null){
RandomListNode temp=new RandomListNode(pHead.label);
src.add(pHead);
dst.add(temp);
pHead=pHead.next;
}
int num=src.size();
//这里需要加一个null是因为之后的next赋值的时候需要的
dst.add(null);
for (int i=0;i<num;i++){
int index;
dst.get(i).next=dst.get(i+1);
if(src.get(i).random!=null){
index=src.indexOf(src.get(i).random);
dst.get(i).random=dst.get(index);
}
else{
dst.get(i).random=null;
}
}
return dst.get(0);
}
}
解法一的优化
解法一实际上就是建立了一个对应关系,src和dst每一个index对应的节点就是复制链表前后的两个节点,所以我们可以直接使用map来建立这个对应的关系
/*
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
*/
import java.util.*;
public class Solution {
public RandomListNode Clone(RandomListNode pHead) {
HashMap<RandomListNode,RandomListNode> h=new HashMap<>();
RandomListNode prev=new RandomListNode(0);
RandomListNode src=pHead;
while(pHead!=null){
RandomListNode temp=new RandomListNode(pHead.label);
prev.next=temp;
h.put(pHead,temp);
pHead=pHead.next;
prev=temp;
}
prev.next=null;
RandomListNode dst=h.get(src);
RandomListNode ans=dst;
while(src!=null){
dst.random=h.get(src.random);
dst=dst.next;
src=src.next;
}
return ans;
}
}