题解 | #复杂链表的复制#

/*
struct RandomListNode {
int label;
struct RandomListNode *next, *random;
RandomListNode(int x) :
label(x), next(NULL), random(NULL) {
}
};
*/

复制链表并拆分
思路： 直接在原链表基础上复制新链表，即让原节点next指向自己的拷贝节点，然后拆分random， 
拷贝节点的random指向其指向的原节点的next，最后，再拆next，让其每一个节点next都指向其原来指向的下一节点，
文字描述有点晦涩，直接上图(图中合并部分，即拷贝过程中，由于空间有限，没有画出原有链表的random指向，
其实原有链表的指向和拷贝之前的一样)
Step1：复制原链表中每一个节点，使得拷贝后的新节点在原节点的下一个节点；
Step2：拷贝后的新节点的random指向节点与原链表节点的random指向节点一致；
Step3：拆分链表，原节点依次连接，拷贝后的新节点依次连接。


* 哈希表
使用哈希表map表示映射关系，其中哈希表的键值key是原节点，value值是复制的新节点。
步骤：
第一步是遍历原链表，利用哈希表映射新节点和旧节点关系，即每遍历一个节点，则复制一个val值相同的新节点，
mp[p]= new Node(p->val)。
第二步是遍历map，复制next和random指针的对应关系，并更新新节点的next和random所指的值，
最后返回新链表的头节点即可，即即mp[p]->next=mp[p->next]和mp[p]->random=mp[p->random]。

class Solution {
public:
    /*
    复制链表并拆分
    思路： 直接在原链表基础上复制新链表，即让原节点next指向自己的拷贝节点，然后拆分random， 
    拷贝节点的random指向其指向的原节点的next，最后，再拆next，让其每一个节点next都指向其原来指向的下一节点，
    文字描述有点晦涩，直接上图(图中合并部分，即拷贝过程中，由于空间有限，没有画出原有链表的random指向，
    其实原有链表的指向和拷贝之前的一样)
    Step1：复制原链表中每一个节点，使得拷贝后的新节点在原节点的下一个节点；
    Step2：拷贝后的新节点的random指向节点与原链表节点的random指向节点一致；
    Step3：拆分链表，原节点依次连接，拷贝后的新节点依次连接。
    */
    /*
    RandomListNode* Clone(RandomListNode* pHead) {
        if(pHead == nullptr) {
            return nullptr;
        }

        //Step1：复制原链表中每一个节点，使得拷贝后的新节点在原节点的下一个节点；
        RandomListNode *pHeadNode = pHead;
        while(pHeadNode != nullptr) {
            RandomListNode *pNewNode = new RandomListNode(pHeadNode->label); //创建头结点
            RandomListNode *pNextNode = pHeadNode->next; //下一个节点
            pHeadNode->next = pNewNode; //尾插法：头结点连接新节点
            pNewNode->next = pNextNode; //新节点连接下一个节点
            pHeadNode = pNewNode->next; //向后移位
        }
        // Step2：拷贝后的新节点的random指向节点与原链表节点的random指向节点一致；
        pHeadNode = pHead;
        while(pHeadNode != nullptr) {
            if (pHeadNode->random != nullptr) {
                pHeadNode->next->random = pHeadNode->random->next;
            }
            pHeadNode = pHeadNode->next->next;
        }
        // Step3：拆分链表，原节点依次连接，拷贝后的新节点依次连接。
        pHeadNode = pHead;
        RandomListNode *pFirstNode = pHead->next;
        RandomListNode *pSecondNode = pHead->next;
        while(pHeadNode != nullptr) {
            pHeadNode->next = pHeadNode->next->next; //第一个节点连接第三节点，断开第二个节点
            pHeadNode = pHeadNode->next; //向后移位
            if(pFirstNode->next != nullptr) {
                pFirstNode->next = pFirstNode->next->next;
                pFirstNode = pFirstNode->next;
            }
        }
        return pSecondNode;
    }
    */

    /*
    * 哈希表
    使用哈希表map表示映射关系，其中哈希表的键值key是原节点，value值是复制的新节点。
    步骤：
    第一步是遍历原链表，利用哈希表映射新节点和旧节点关系，即每遍历一个节点，则复制一个val值相同的新节点，
    mp[p]= new Node(p->val)。
    第二步是遍历map，复制next和random指针的对应关系，并更新新节点的next和random所指的值，
    最后返回新链表的头节点即可，即即mp[p]->next=mp[p->next]和mp[p]->random=mp[p->random]。
    */
    RandomListNode* Clone(RandomListNode* pHead) {
        if(pHead == nullptr) {
            return nullptr;
        }

        unordered_map<RandomListNode*, RandomListNode*> mpNode;
        RandomListNode* pHeadNode = pHead;
        while(pHeadNode != nullptr) {
            mpNode[pHeadNode] = new RandomListNode(pHeadNode->label);
            pHeadNode = pHeadNode->next;
        }

        pHeadNode = pHead;
        while(pHeadNode != nullptr) {
            if(pHeadNode->next != nullptr) {
                mpNode[pHeadNode]->next = mpNode[pHeadNode->next]; // 拷贝节点连接下一个节点
            }
            if(pHeadNode->random != nullptr) {
                mpNode[pHeadNode]->random = mpNode[pHeadNode->random];
            }
            pHeadNode = pHeadNode->next;
        }

        return mpNode[pHead];
    }
};