【剑指Offer-分解让复杂问题简单化】面试题35：复杂链表的复制

题目描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

思路

可以将该问题的求解分为3步：
1、对于原始链表中的每个节点复制该节点放在原节点的后面，如下图

2、设置复制节点的下一个节点。如果原节点N随机指向的节点为S，则N'随机指向的节点为S->next，如下图

3、经过前两步的链表包含了原始节点和复制的节点，这一步将它们分离：原始链表中的节点下标为奇数（下标从1开始），复制后的链表中的节点下标为偶数，如下图

代码如下：

/*
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;
        
        /*1、添加复制后的节点*/
        RandomListNode* curNode = pHead;
        while(curNode!=nullptr)
        {
            RandomListNode* clonedNode = new RandomListNode(curNode->label);
            RandomListNode* nextNode = curNode->next;
            curNode->next = clonedNode;
            clonedNode->next = nextNode;
            curNode = nextNode;
        }
        
        /*2、连接随机节点*/
        curNode = pHead;
        while(curNode!=nullptr)
        {
            RandomListNode* clonedNode = curNode->next;
            if(curNode->random!=nullptr)
                clonedNode->random = curNode->random->next;
            curNode = clonedNode->next;
        }
        
        /*3、分离原始链表和复制后的链表*/
        RandomListNode* curRaw = pHead;    //原始链表的头结点
        RandomListNode* clonedHead = pHead->next;    //复制的链表的头结点
        RandomListNode* curCloned = clonedHead;
        /*while(curRaw!=nullptr)    //该方法也可以通过
        {
            curCloned = curRaw->next;
            curRaw->next = curCloned->next;
            if(curCloned->next!=nullptr)
                curCloned->next = curCloned->next->next;
            curRaw = curRaw->next;
        }*/
        
        while(curCloned->next!=nullptr)   //注意终止条件
        {
            curRaw->next = curRaw->next->next;
            curRaw = curRaw->next;
            curCloned->next = curCloned->next->next;
            curCloned = curCloned->next;
        }
        curRaw->next = nullptr;    //使用上面的循环一定要加上这一句，使用注释的循环不需要加
        return clonedHead;
    }
};