輸入一個(gè)復(fù)雜鏈表（每個(gè)節(jié)點(diǎn)中有節(jié)點(diǎn)值，以及兩個(gè)指針，一個(gè)指向下一個(gè)節(jié)點(diǎn)，另一個(gè)特殊指針指向任意一個(gè)節(jié)點(diǎn)）。
返回一個(gè)該鏈表的深度拷貝.

思路:

1. 遍歷該鏈表,復(fù)制每一個(gè)節(jié)點(diǎn),插入到當(dāng)前節(jié)點(diǎn)的后面.形成如下鏈表.
   1->1'->2->2'....
2. 將每個(gè)拷貝節(jié)點(diǎn)的隨機(jī)指針域,指向原節(jié)點(diǎn)(即拷貝節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn))的隨即指針域指向(注意隨機(jī)指針域可能為空)的下一個(gè)節(jié)點(diǎn).即1的隨機(jī)指針域指向3,則1'的隨機(jī)指針域指向3的下一個(gè)指針3'.
3. 拆分鏈表,返回1'->2'->3'...

代碼如下:

/*
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 runner=pHead;
        RandomListNode copyCat=null;
        //First round: make copy of each nodes
        while(runner!=null){
            copyCat=new RandomListNode(runner.label);
            copyCat.next=runner.next;
            runner.next=copyCat;
            runner=copyCat.next;
        }
        
        //Second Round: assign random pointers for the copy nodes
        runner=pHead;       
        while(runner!=null){
            copyCat=runner.next;
            //notice random pointers could be null
            copyCat.random=runner.random==null?null:runner.random.next;
            runner=runner.next.next;
        }
        
        //Third round: restore the original list, and extract the copy list.
        runner=pHead;
        pHead=runner.next;
        while(true){
            copyCat=runner.next;
            runner.next=copyCat.next;
            runner=copyCat.next;
            if(runner==null){
                break;
            }
            else{
               copyCat.next=runner.next;
            }           
        }
        return pHead;
    }
}