連結清單5：複雜連結清單的複制

題目：輸入一個複雜連結清單（每個節點中有節點值，以及兩個指針，一個指向下一個節點，另一個特殊指針指向任意一個節點），傳回結果為複制後複雜連結清單的head。（注意，輸出結果中請不要傳回參數中的節點引用，否則判題程式會直接傳回空）

思路：詳見劍指offer。對于建立的一個連結清單，要進行周遊，采取
RandomListNode dummy=new RandomListNode(-1);
RandomListNode list=dummy;
的方式。而對于一個已經存在的需要進行周遊利用最終又需要傳回的連結清單，要保持頭結點，統一采取這種方式：
public RandomListNode Clone(RandomListNode pHead){
RandomListNode pCur = pHead;
while(pCur!=null){

技巧：對于一個傳入的連結清單結點，既要進行周遊處理最終又要傳回頭結點，需要先建立一個變量，将頭結點指派給這個變量，之後周遊操作對這個變量進行操作，即找一個代理來做周遊而保持頭結點不便。例如：
public RandomListNode Clone(RandomListNode pHead){
        if(pHead==null)
            return null;
        RandomListNode pCur = pHead;
        //複制next 如原來是A->B->C 變成A->A'->B->B'->C->C'
        while(pCur!=null){
            RandomListNode node = new RandomListNode(pCur.label);
            node.next = pCur.next;
            pCur.next = node;
            pCur = node.next;
        }

特殊的：相同的代碼在LeetCode的oj上通過了，但是在牛客上面通不過的問題。一下代碼在LeetCode的oj上面通過了。
**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
**/        
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head)
    {
        //特殊輸入：空連結清單
        if(head==null) return null;
        //首先複制所有的結點形成一個長的連結清單head2
        RandomListNode head2 =this.cloneNode(head);
        //設定長連結清單中的引用關系
        RandomListNode head3=this.connectNode(head2);
        //拆分連結清單，得到指派結點組成的連結清單，即偶數位置的結點，并将其連接配接起來2,4,6,8……
        return this.splitNode(head3);
       }
    
    //輸入一個連結清單，複制每一個結點放在原結點的後面，最後傳回這個長的連結清單
    public RandomListNode cloneNode(RandomListNode pHead){
		//記住第一個結點，用于傳回
        RandomListNode head=pHead;
        while(pHead!=null){
            //建立結點
            RandomListNode newNode=new RandomListNode(pHead.label);
            //重建插入結點後的關聯關系
            newNode.next=pHead.next;
            pHead.next=newNode;
            pHead=pHead.next.next;
        }
        return head;
    }
    
    //輸入一個長連結清單，為裡面的複制結點設定關聯關系
    public RandomListNode connectNode(RandomListNode pHead){
        //要傳回連結清單必須記住第一個結點
        RandomListNode head=pHead;
        
        //周遊原始連結清單，從第一個結點開始，1,3,5,7,9……
        while(pHead!=null){
            //特别注意：有的結點的random的屬性可能是null,此時pHead.random.next必然空指針異常
            if(pHead.random!=null){
                pHead.next.random=pHead.random.next;
            }
            pHead=pHead.next.next;
        }
        return head;
        
    }
        
    //輸入一個連結清單，将其中偶數位置的結點取出來拆分後連接配接成為新的連結清單
    public RandomListNode splitNode(RandomListNode pHead){
        //保留第一個偶數結點作為頭結點以便進行傳回,技巧：對于每一條建立的連結清單建立dummy，list兩個變量
        RandomListNode dummy=new RandomListNode(-1);
        RandomListNode list=dummy;
        
         while(pHead!=null){
	        list.next=pHead.next;
	        list=list.next;
	        pHead=pHead.next.next;
	     }
        return dummy.next;
    }
}