复杂链表的复制

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点）。
返回一个该链表的深度拷贝.

思路:

1. 遍历该链表,复制每一个节点,插入到当前节点的后面.形成如下链表.
   1->1'->2->2'....
2. 将每个拷贝节点的随机指针域,指向原节点(即拷贝节点的上一个节点)的随即指针域指向(注意随机指针域可能为空)的下一个节点.即1的随机指针域指向3,则1'的随机指针域指向3的下一个指针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;
    }
}