/*

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 == nullptr)

        {

            return nullptr;

        }

        //将链表每个结点复制一个克隆，放在该节点的后一位

        RandomListNode *pNode = pHead;

        while(pNode != nullptr)

        {

            RandomListNode *pClone = new RandomListNode(pNode->label);

            pClone->next = pNode->next;

            pClone->random = nullptr;

            pNode->next = pClone;

            pNode = pClone->next;

        }

        //设置克隆结点的random

        pNode = pHead;

        while(pNode != nullptr)

        {

            RandomListNode *pClone = pNode->next;

            if(pNode->random != nullptr)

            {

                pClone->random = pNode->random->next;

            }

            pNode = pClone->next;

        }

        //将链表拆分

        pNode = pHead;

        RandomListNode *pCloneHead = pHead->next;

        while(pNode->next != nullptr)

        {

            RandomListNode *ptmp = pNode->next;

            pNode->next = ptmp->next;

            pNode = ptmp;

        }

        return pCloneHead;

    }

};