牛客 剑指offer 复杂链表的复制

题目

代码

/*
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(NULL==pHead){
          
   
            return pHead;
        }
        RandomListNode* currentNode=pHead;
        while(currentNode){
          
   
            RandomListNode* cloneNode = new RandomListNode(currentNode->label);
            cloneNode->next=currentNode->next;
            currentNode->next=cloneNode;
            currentNode=cloneNode->next;
        }
        //对每个节点都进行复制。A复制成A。
        //并把A放在A的后面。
        currentNode=pHead;
        while(currentNode){
          
   
            RandomListNode*nextNode=currentNode->next;
            if(currentNode->random){
          
   
                nextNode->random=currentNode->random->next;
            }
            currentNode=nextNode->next;
        }
        //这里是把A和A的random指针域处理好。
        RandomListNode *pCloneHead = pHead->next;
        RandomListNode *tmp; 
        currentNode = pHead;
        while(currentNode->next){
          
   
            tmp = currentNode->next;
            currentNode->next =tmp->next;
            currentNode = tmp;
        }
        //这里是把奇数位和偶数位的分开链接起来。
        return pCloneHead;
    }
};