复杂链表的复制

方法一：哈希表（unordered_map）:

图解：

思路：

1.假如链表没有随机指针, 我们的拷贝方式很简单, 只要先创建一个哨兵节点, 然后遍历一下给定链表, 创建新节点, 并不断和上个节点连接

2.本题的难点就在于每个节点还有一个指向空或其它节点的指针, 一种比较直观的想法就是先把整条链表连起来, 然后再挨着改变指针,

3.因此我们可以用哈希表来存放指针的映射关系, 然后根据将随机指针指向原链表随机指针映射在新链表的位置

4.算法实现：首先创建一个哨兵节点, 遍历一次原链表, 先将除随机指针外的部分创建并连接, 同时用哈希表记录指针之间的映射, 最后遍历一次哈希表, 将随机指针指向对应的位置

代码：

/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead) {
        //创建一个哈希表（无序的映射关系）：unordered_map<原链表的节点的指针，映射的节点的的指针>，即将原先链表中的节点与克隆的节点进行一一映射
        unordered_map<RandomListNode*,RandomListNode*> map;
        //在创建一个新的链表和删除节点操作的时候，为了方便处理头节点，可以设置一个虚的头结点，将pre指向虚的头结点，让cur指向原链表的头结点
        RandomListNode* dummynode=new RandomListNode(-1);
        RandomListNode* pre=dummynode;
        RandomListNode* cur=pHead;
        //先遍历原链表，将原链表中的节点克隆出一个新的节点，将原节点与克隆出的节点进行一一映射关系，再将新形成的链表先根据next指针形成线性的关系
        while(cur!=NULL){
            RandomListNode* clone=new RandomListNode(cur->label);
            map[cur]=clone;
            pre->next=clone;
            pre=pre->next;
            cur=cur->next;
        }
        //再遍历整个哈希表：for(数据类型 需要访问的数据：访问的数据所在的容器) auto表示会根据输入的具体的值进行自动匹配数据类型
        //因为要将克隆的节点的随机指针指向对应的位置，可以先根据映射关系，看原链表的这个节点的随机之好着呢指向的节点，再将克隆的节点指向原链表对应的节点的随机指针指向的节点的映射到新生成的链表中的节点
        for(auto& [key,value]:map){
            value->random=(key->random==NULL)?NULL:map[key->random];
        }
        return dummynode->next;
    }

};

方法二：将复制的表穿插在原来的表中，再进行拆分

图解：

链接

思路：

step 1：遍历链表，对每个节点新建一个拷贝节点，并插入到该节点之后。

step 2：使用双指针再次遍历链表，两个指针每次都移动两步，一个指针遍历原始节点，一个指针遍历拷贝节点，拷贝节点的随机指针跟随原始节点，指向原始节点随机指针的下一位。

step 3：再次使用双指针遍历链表，每次越过后一位相连，即拆分成两个链表。

代码：

/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead) {
        //判断一下如果是空链表，就不需要进行复制了，直接返回NULL
        if(pHead==NULL){
            return pHead;
        }
        //定义一个cur指针指向原链表的头结点
        RandomListNode *cur=pHead;
        //遍历整个原链表
        while(cur!=NULL){
            //将原链表的每个节点进行复制克隆
            //将克隆出来的新节点连在原链表对应的节点的后面
            RandomListNode *clone=new RandomListNode(cur->label);
            clone->next=cur->next;
            cur->next=clone;
            cur=clone->next;
        }
        //设置三个指针：*old指向链表的表头，*now指向链表的第二个节点，*newhead用来记录复制出来的新表的头结点
        RandomListNode *old=pHead;
        RandomListNode *now=pHead->next;
        RandomListNode *newhead=pHead->next;
        //将链表的克隆出来的节点的随机指针指向原先的节点的随机指针指向节点的后一个节点
        //注意需要特判空节点，即如果发现原链表的节点的随机指针是指向空节点的，
        //那么就直接让新的节点的随机指针也指向空节点，否则就会出现now->random=old->random->next,由于old->next就已经是空节点了，所以当null->next的时候就会报错！！！！！！！，一旦遇到需要连接到下下个节点的时候，就必须进行特判下一个节点是不是空节点，如果下一个是空节点，就不能赋值为old->next->next!!
        while(old!=NULL){
            now->random=(old->random==NULL)?NULL:old->random->next;
            if(old->next){
                 old=old->next->next;
            }
            if(now->next){
                now=now->next->next;
            }
        }
        
        old=pHead;
        now=pHead->next;
        //拆分新旧表，进行特判是不是空节点，如果不是空节点，就让old->next=old->next->next
        //now->next=now->next->next
        while(old!=NULL){
           if(old->next) old->next=old->next->next;
           if(now->next) now->next=now->next->next;
            old=old->next;
            now=now->next;
        }
        //返回新的复制出来的链表的头结点
         return newhead;
    }

};