题目描述:
给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。
要求返回这个链表的深度拷贝。
思路:
先遍历链表,将每个节点对应的随机指针指向的对象利用HashMap存起来,key的值就为节点的在链表里面的位置,Value的值是随机指针指向的对象
再把原链表的节点对应的在链表中的位置存起来,key为节点对象,然后将节点的label取出来新建节点,存起来
再次遍历链表,处理随机指针
这是第一种用HashMap的办法,但是性能不行,还有优化的空间,之后我再研究研究看能不能改改
public static RandomListNode copyRandomList(RandomListNode head) {
HashMap randomMap = new HashMap<>();//随机节点
HashMap newMap = new HashMap<>();//新的节点
HashMap oldMap = new HashMap<>();//原表的节点
RandomListNode result = head;
if(head==null)
return head;
if(head.next==null){
RandomListNode it = new RandomListNode(head.label);
if (head.random!=null){
it.random = it;//指向自己
}
return it;
}
//迭代
RandomListNode iterator = head;
int i = 0;
while(iterator!=null){
//将第几位对应的随机指针存起来
randomMap.put(i,iterator.random);
//原链表节点对应的位置存起来
oldMap.put(iterator,i);
//新建节点,复制
RandomListNode node = new RandomListNode(iterator.label);
newMap.put(i,node);
if(i==0){
//第一个
result = node;
}
iterator = iterator.next;
i++;
}
i = 0;
iterator = head;
while(iterator!=null){
if(i>0)
newMap.get(i-1).next = newMap.get(i);
//检测原节点的随机指针是否为空
if(oldMap.get(randomMap.get(i))!=null){
//获得原链表节点的随机指针指向的对象的位置
int random = oldMap.get(randomMap.get(i));
//赋值
newMap.get(i).random = newMap.get(random);
}else {
//随机指针为空的情况
newMap.get(i).random = null;
}
iterator = iterator.next;
i++;
}
return result;
}
static class RandomListNode {
int label;
RandomListNode next, random;
RandomListNode(int x) { this.label = x; }
}
还有不用HashMap的,性能应该好点我还没AC.AC了再传上来...不知道怎么错了