这是一个leetcode上accepted，可是自己却觉得代码写错了的故事。
题目是这样的：
image
当我提交这样的代码时，竟然accepted了。
image
可是这样的方式明显会产生野指针啊，就是random指向的地址就根本不在list中，虽然他们的值一样，可是地址是完全不一样的。为了验证我的猜想，开始了虐自己的道路。
我的主要思想就是看random指向的那个是不是list中的那个，因此我直接用了==。若是大佬觉得有何不妥，欢迎随时指正，在此谢过。代码如下：
public class Test1 {
private static class RandomListNode {
private int label;
public RandomListNode next=null, random=null;
public RandomListNode(int x) { this.label = x; }
}
public static void RandomListNodeNext(RandomListNode node1,RandomListNode node2){
node1.next=node2;
}
public static void RandomListNodeRandom(RandomListNode node1,RandomListNode node2){
node1.random=node2;
}
public static void main(String []args) {
RandomListNode head=new RandomListNode(0);
RandomListNode node1=new RandomListNode(1);
RandomListNode node2=new RandomListNode(2);
RandomListNode node3=new RandomListNode(3);
RandomListNode node4=new RandomListNode(4);
RandomListNode node5=new RandomListNode(5);
RandomListNodeNext(head,node1);
RandomListNodeNext(node1,node2);
RandomListNodeNext(node2,node3);
RandomListNodeNext(node3,node4);
RandomListNodeNext(node4,node5);
RandomListNodeRandom(head,node5);
RandomListNodeRandom(node2,node1);
RandomListNodeRandom(node4,head);
RandomListNode copy=copyRandomListNode2(head);
System.out.println("被copy的链表");
if(head.random==node5)
System.out.println("指向应该如此");
System.out.println(head.random);
System.out.println(node5);
RandomListNode copy2=copy;
while(copy2.next!=null)
copy2=copy2.next;
System.out.println(copy2.label);
if(copy.random==copy2)
System.out.println("指向应该如此");
else
System.out.println("有野指针");
System.out.println(copy.random);
System.out.println(copy2);
while(head!=null)
{
System.out.println(head.label);
System.out.println("next"+head.next);
System.out.println("random"+head.random);
head=head.next;
}
while(copy!=null)
{
System.out.println(copy.label);
System.out.println("next"+copy.next);
System.out.println("random"+copy.random);
copy=copy.next;
}
System.out.println("Hello World");
}
//复制有random指针的错误方式，但是在leetcode上竟然accepted。。。。
public static RandomListNode copyRandomList(RandomListNode head) {
if(head==null)
return head;
RandomListNode headcopy=new RandomListNode(0);
RandomListNode headcopyindex=headcopy;
while(head!=null)
{
RandomListNode node=new RandomListNode(head.label);
if(head.random!=null)
{
RandomListNode noderandom=new RandomListNode(head.random.label);
node.random=noderandom;
}
headcopyindex.next=node;
headcopyindex=headcopyindex.next;
head=head.next;
}
return headcopy.next;
}
//正确方式
public static RandomListNode copyRandomListNode2(RandomListNode head){
if(head==null)
return head;
RandomListNode headcopy=new RandomListNode(0);
RandomListNode headcopy2=headcopy;
RandomListNode head2=head;
//首先将链表中的数都copy下来
while(head!=null)
{
RandomListNode node=new RandomListNode(head.label);
head=head.next;
headcopy2.next=node;
headcopy2=headcopy2.next;
}
//将链表中的random指针copy过来
headcopy2=headcopy.next;
head=head2;
while(head2!=null)
{
if(head2.random!=null)
{
//每次都需要从链表的头部开始遍历
RandomListNode index=head;
RandomListNode index2=headcopy.next;
while(index!=null){
if(index==head2.random)
break;
//步长一致
index=index.next;
index2=index2.next;
}
headcopy2.random=index2;
}
//用来指向比较的两个链表中的节点
head2=head2.next;
headcopy2=headcopy2.next;
}
return headcopy.next;
}
}
采用copyRandomList方式，运行的效果如下：
image
采用copyRandomListNode2，运行效果如下：
image
当然，正确版本也accepted了。看来leetcode上的测试不全啊。。。。
image
