输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),
//方案一:1 先复制一个链表,2在把random赋引用
public class Solution {
public RandomListNode Clone(RandomListNode pHead)
{
if(pHead==null)
return null;
RandomListNode root = new RandomListNode(-1);
RandomListNode temp = root;
RandomListNode cur=pHead;
while(cur!=null){
temp.next=new RandomListNode(cur.label);
temp=temp.next;
cur=cur.next;
}
RandomListNode temp1=pHead;
RandomListNode temp2=null;
RandomListNode temp3=root.next;
RandomListNode temp4=null;
while(temp1!=null){
if(temp1.random==null){
temp1=temp1.next;
temp3=temp3.next;
continue;
}
temp2=pHead;
temp4=root.next;
while(temp1.random!=temp2){
temp2=temp2.next;
temp4=temp4.next;
}
temp3.random=temp4;
temp1=temp1.next;
temp3=temp3.next;
}
return root.next;
}
}
//方案二:
public class Solution {
public RandomListNode Clone(RandomListNode pHead)
{
if(pHead==null)
return null;
RandomListNode cur=pHead;
while(cur!=null){
RandomListNode node=new RandomListNode(cur.label);
node.next=cur.next;
cur.next=node;
cur=node.next;
}
cur=pHead;
while(cur!=null){
if(cur.random==null){
cur=cur.next.next;
continue;
}else{
cur.next.random=cur.random.next;
cur=cur.next.next;
}
}
cur=pHead;
RandomListNode root=cur.next;
RandomListNode temp=null;
while(cur!=null){
temp=cur.next;
cur.next=temp.next;
if(temp.next==null)
temp.next=null;
else
temp.next=temp.next.next;
cur=cur.next;
}
return root;
}
}