剑指offer——复杂链表的复制C++

默认所有结点的random指针不会指向不在链表中的独立结点。
两种方法：递归和循环
递归：需要通过一个辅助的map来实现，这个map是用来处理random指针指向的结点的，防止重复新建node。在递归函数中根据当前结点的值new一个结点指针，在map记录当前指针对应的指针是新建的这个。然后递归next结点。当next都递归完后，判断当前结点的random是否为空，如果不为空，就将新建的这个结点的random指向map存储的原结点的random指针的拷贝指针。最后返回新建的指针即可。

循环：三步法，每一步都不简单，每一步都有细节，好处就是不用O(N)空间复杂度的map
1.复制单链表，将A1插入到A后面，A2前面
2.连接random域，A1.random = A.random.next
3.拆分单链表，改变A1的next为A的next的next
定义一个currentnode来指向当前遍历到的结点，初始赋值为pHead
第一步：当currentnode为空时结束循环，根据currennode来new一个克隆结点，并且定义一个nextnode来保存当前结点的下一个结点（防止等下改变next后找不到后序的结点）。将当前结点的next改为克隆结点，将克隆结点的next改为nextnode，currentnode=nextnode。
第二步：将currentnode重新指向pHead，重新回到这条链的起点处。这次currentnode指的全是原先链表中的结点，不是克隆结点，所以跳着访问。找原链表上的所有结点random指针是否为空，如果不为空，就将当前结点的random指针的next赋给当前结点的拷贝（也就是当前结点的next）的random。最后使currentnode指向它next的next。
第三步：将克隆结点的next指向克隆结点next的next，记得返回pHead的next，这才是克隆链表的头结点。

/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
public:
    //map<RandomListNode*,RandomListNode*> ma;
    
    RandomListNode* Clone(RandomListNode* pHead)
    {
        //首先我们要知道所有random结点都是在这条链表里的，不存在一个独立结点被random指到
        //所有random结点都能被next指到
        //所以先递归复制所有next指针指向的结点，并将其存入ma中，可以通过原结点找到深拷贝的结点
        //每一轮递归复制完next后，从ma中拿出原结点的random复给现在结点的random
        /*if(pHead == NULL) return NULL;
        RandomListNode* node = new RandomListNode(pHead->label);
        ma[pHead] = node;
        node->next = Clone(pHead->next);
        node->random = NULL;
        if(pHead->random) node->random = ma[pHead->random];
        return node;*/
        
        //法2：三步法，通过next指针关联，不用辅助map
        //复制单链表，将A1插入到A后面，A2前面
        //连接random域，A1.random = A.random.next
        //拆分单链表，改变A1的next为A的next的next
        if(pHead == NULL) return NULL;
        RandomListNode* currentNode = pHead;
        while(currentNode != NULL){
            RandomListNode* cloneNode = new RandomListNode(currentNode->label);
            RandomListNode* nextNode = currentNode->next;
            currentNode->next = cloneNode;
            cloneNode->next = nextNode;
            currentNode = nextNode;
        }
        
        currentNode = pHead;
        while(currentNode != NULL){
            //这个判断必须加！
            if(currentNode->random != NULL){//如果原结点random指针不为空
                //那么复制的结点的random就指向原结点的random的复制结点
                currentNode->next->random = currentNode->random->next;
            }
            currentNode = currentNode->next->next;
        }
        
        currentNode = pHead;
        RandomListNode* pCloneHead = pHead->next;
        while(currentNode != NULL){
            RandomListNode* cloneNode = currentNode->next;
            currentNode->next = cloneNode->next;
            cloneNode->next = cloneNode->next == NULL ? NULL : cloneNode->next->next;
            currentNode = currentNode->next;
        }
        return pCloneHead;
    }
};