/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead)
    {
        RandomListNode* pNode = pHead;
        //0.要考虑空节点，不写的话，程序就报错了。就会出现数组越界的情况！！！！！！！
        if(pNode == nullptr) return nullptr;
        //1.复制节点，插入到节点的后方
        copyNode( pNode);
        //2.还原原节点的random指针
        restoreNodeRandom(pNode);
        //3.拆分
        return splitNode(pNode);
    }
    
    void copyNode(RandomListNode* pHead)
    {
        RandomListNode* pNode = pHead;
        
        while(pNode != nullptr)
        {
            //1.1新建一个克隆节点
            RandomListNode* pClone = new RandomListNode(pNode->label);
            pClone->next = pNode->next;
            pNode->next = pClone;
            //1.2更新当前的节点
            pNode = pClone->next;               
        }
    }
    
    void restoreNodeRandom(RandomListNode* pHead)
    {
        RandomListNode* pNode = pHead;
        
        //进行循环判断
        while(pNode != nullptr)
        {
            RandomListNode* pClone = pNode->next;
            //2.1判断当前节点是否有random
            if(pNode->random)
            {
                pClone->random = pNode->random->next;
            }
            //2.2更新当前的节点
            pNode = pClone->next;
        }
    }
    
    RandomListNode* splitNode(RandomListNode* pHead)
    {
        RandomListNode* pNode = pHead;
        //result!!!!!
        RandomListNode* result =pNode->next;
        while(pNode != nullptr)
        {
            RandomListNode* pClone = pNode->next;
            //拆分1.
            pNode->next= pClone->next;
            //更新当前节点
            pNode = pNode->next;
            //拆分2.
            if(pNode)
            {
                pClone->next = pNode->next;
            } 
        }
        //返回的不是pClone!!!
        return result;
    }
};