题解 | #复杂链表的复制#

/* 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; if(pHead.next == null) { RandomListNode newNode = new RandomListNode(pHead.label); return newNode; }

    //先初始化和链表大小相同的数组
    int num = 0;
    RandomListNode temp = pHead;
    while(temp.next != null) {
    	num++;
    	temp = temp.next;
    }
    if(temp.next == null) {
    	num++;
    }
    RandomListNode[] rArray = new RandomListNode[num];
    
    //再把每个结点的next赋值进去
    RandomListNode temp1 = pHead;
    for(int i = 0;i < rArray.length;i++) {
    	rArray[i] = new RandomListNode(temp1.label);
    	temp1 = temp1.next;
    }
    for(int i = 0;i < rArray.length;i++) {
    	if(i < rArray.length-1) rArray[i].next = rArray[i+1];
    }
    
    //最后把每个结点的random赋值进去
    RandomListNode temp2 = pHead;
    RandomListNode temp3 = pHead;
    int index = 0;
    int rIndex = 0;
    while(temp2.next != null) {
    	if(temp2.random == null) {
    		rArray[index].random = null;
    		index++;
    		temp2 = temp2.next;
    	}
    	else {        		
    		if(temp3.next == temp2.random) {
    			rIndex++;
    			rArray[index].random = rArray[rIndex];
    			temp3 = pHead;
    			temp2 = temp2.next;
    			rIndex = 0;
    			index++;
    		}else {
    			temp3 = temp3.next;
    			rIndex++;
    		}
    	}
    }
    
    return rArray[0];
}

}