复杂链表的复制
尝试一
结果:case通过率为0.00%
code:
/*
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
*/
public class Solution {
public RandomListNode Clone(RandomListNode pHead)
{
/*特殊情况处理*/
if(pHead==null){
return null;
}
RandomListNode target=new RandomListNode(pHead.label);
myClone(pHead,target);
return target;
}
private void myClone(RandomListNode src,RandomListNode target){
/*递归结束标识*/
if(src==null){
return ;
}
target=new RandomListNode(src.label);
target.next=src.next;
target.random=src.random;
myClone(src.next,target.next);
myClone(src.random,target.random);
}
}
分析:java里面对象其实都是传值的(引用reference的值)。在private void myClone(RandomListNode src,RandomListNode target)
中,target传的只是引用(引用是引用,对象是对象)。一开始target的确是指向我们想操作的那个对象的,可是我们有重新target=new RandomListNode(src.label);
了。接下来,你在怎么操作target都不会 影响原来的对象了(操作对象是操作对象,操作引用是操作引用)。
下面举个例子:
public static void main(String[] args) {
Main m=new Main();
int[] test={1,2};
m.test(test);
System.out.println(test);
}
private void test(int []a){
a=new int[1];
}
问:现在test的值或者长度为多少?
长度是2,不是一。因为
a=new int[1];
操作的是reference(引用),而不是应用指向的对象。
尝试二
result:case通过率为0.00%
code:
/*
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
*/
public class Solution {
public RandomListNode Clone(RandomListNode pHead)
{
//return pHead;
/*特殊情况处理*/
if(pHead==null){
return null;
}
RandomListNode target=new RandomListNode(pHead.label);
myClone(pHead,target);
return target;
}
private void myClone(RandomListNode src,RandomListNode target){
/*递归结束标识*/
if(src==null){
return ;
}
target.label=src.label;
if(src.next!=null) {
//需要在堆上分配空间
target.next = new RandomListNode(src.next.label);
myClone(src.next,target.next);
}
if(src.random!=null) {
//需要在堆上分配空间
target.random = new RandomListNode(src.random.label);
myClone(src.random,target.random);
}
}
}
分析:我理解错题意了。以为random
不能指向next 那些节点,然后这样就可以像二叉树那样处理了。然而并不是,还可以像下面那样:
(这道题就应该强调一下的,或者举个例子不然问题发生了,找半天都不知道是什么原因。不过,上面的代码应该是可以复制一棵二叉树的)。
更正:链表是线性结构。如下:
尝试三
result:答案正确:恭喜!您提交的程序通过了所有的测试用例
code:
/*
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
*/
public class Solution {
public RandomListNode Clone(RandomListNode pHead)
{
if(pHead==null){
return null;
}
RandomListNode target=new RandomListNode(pHead.label) ;
RandomListNode iterator=pHead;
RandomListNode iteratorT=target;
/*拷贝next*/
while(iterator.next!=null){
iteratorT.next=new RandomListNode(iterator.next.label);
iterator=iterator.next;
iteratorT=iteratorT.next;
}
/*改变random。iterator、iteratorT是遍历next的指针*/
iterator=pHead;
iteratorT=target;
while(iterator!=null){
/*递归求random。需要从头开始遍历。也需要用两个指针分别指向pHead和target*/
if(iterator.random!=null){
RandomListNode iterator1=pHead;
RandomListNode iterator2=target;
while(iterator1!=null){
if(iterator1==iterator.random){
break;
}
iterator1=iterator1.next;
iterator2=iterator2.next;
}
/*找到next之后,改变连接*/
iteratorT.random=iterator2;
}
iterator=iterator.next;
iteratorT=iteratorT.next;
}
return target;
}
}
分析:先拷贝next。再改变random的指向。
结论
- 链表是线性结构