/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead)
    {
        if(pHead == NULL)
            return NULL;
        CloneNode(pHead);
        CloneRandom(pHead);
        return DevideNode(pHead);
    }
    
    void CloneNode(RandomListNode* pHead) //复制结点并且添入原有链表
    {
        RandomListNode* pnode = pHead;//pnode为指向原始链表结点的指针
        while(pnode != NULL)
        {
            RandomListNode* node = new RandomListNode(1);//node为指向复制链表结点的指针
            node->label = pnode->label;
            node->next = pnode->next;
            pnode->next = node;//完成插入
            pnode = node->next;
        }
         
    }
    
    void CloneRandom(RandomListNode* pHead)//复制random指针
    {
        RandomListNode* pnode = pHead;//pnode为指向原始链表结点的指针
        RandomListNode* node = pnode->next;
        while(pnode != NULL)
        {
            node = pnode->next;//node为指向复制链表结点的指针
            if(pnode->random != NULL)
            {
                node->random = pnode->random->next;
            }
            
            pnode = pnode->next->next;
        }
    }
    
    RandomListNode* DevideNode(RandomListNode* pHead)//拆分成两个链表并返回指向复制链表的头结点
    {
        RandomListNode* pnode = pHead;
        RandomListNode* node = NULL;
        RandomListNode* head = NULL;
        if(pnode != NULL)//处理第一个结点，防止只有一个结点的情况
        {
            head = node = pnode->next;//初始化各个指针
            pnode->next = node->next;
            pnode = pnode->next;
        }
        while(pnode != NULL)//原始结点先向后移动，复制结点后移
        {
            node->next = pnode->next;//进入循环说明不止一个结点
            node = node->next;
            pnode->next = node->next;
            pnode = pnode->next;
        }
        
        return head;
    }
};