題目描述
輸入一個(gè)復(fù)雜鏈表（每個(gè)節(jié)點(diǎn)中有節(jié)點(diǎn)值，以及兩個(gè)指針囤攀，一個(gè)指向下一個(gè)節(jié)點(diǎn)软免，另一個(gè)特殊指針指向任意一個(gè)節(jié)點(diǎn)），返回結(jié)果為復(fù)制后復(fù)雜鏈表的head焚挠。（注意膏萧，輸出結(jié)果中請(qǐng)不要返回參數(shù)中的節(jié)點(diǎn)引用，否則判題程序會(huì)直接返回空）
指針的處理要特別小心蝌衔，在尾部和random為null的時(shí)候容易出現(xiàn)NullPointerException
/*
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 p = pHead;
//第一步榛泛，復(fù)制節(jié)點(diǎn)鏈接在原節(jié)點(diǎn)后邊
while(p!=null){
RandomListNode node = new RandomListNode(p.label);
node.next = p.next;
p.next = node;
p=node.next;
}
//第二步，設(shè)置random指針
p=pHead;
RandomListNode p2=pHead.next;
while(p!=null){
if(p.random!=null){
p2.random=p.random.next;
}
p=p.next.next;
if(p!=null){
p2=p.next;
}
}
//第三步噩斟，拆分鏈表
p=pHead;
RandomListNode newHead = pHead.next;
p2=pHead.next;
while(p!=null){
p.next=p2.next;
p=p.next;
if(p!=null){
p2.next=p.next;
}else{
p2.next=null;
}
p2=p2.next;
}
return newHead;
}
}
