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

题意分析

• 感觉这个题目意思还是比较难理解的。但是幸好给出了样例的相关解释，就是给出一个固定的链表，需要我们对这条链表进行深拷贝，然后返回一个新的链表的头即可。

• 解决这个题目的关键，首先是需要理解什么是深拷贝。深拷贝：从堆内存中开辟一个新的区域存放新对象，对对象中的子对象进行递归拷贝,拷贝前后的两个对象互不影响。看不懂？简单来说就是让你复制出另外一条新的与原链表结构相同的一条链。但是这两条链之间不能有共用的内存。再简单来说就是在这条新的链表里面的每个节点都需要我们new出来。

大家可以结合下面这张图来更好地理解深拷贝

思路分析

思路一

• 这个题目理解好题目意思应该就比较好做了。但是我们会发现，我们遍历这个链表的话，其实这个节点就是上一个节点的next节点，但是我们如果一时之间想不到什么好的解决办法，那么就可以用一个map先预存储每个节点。这里的map存储的是旧节点对应的新节点。然后再进行一遍遍历，从而得到最终的链表，不过我们还需要定义两个中间节点帮我们更好地实现。

• 具体请看代码

class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead) {
        // 先判断是否为空
        if(pHead==NULL){  
            return NULL;
        }
        // new出最终的头节点
        RandomListNode* ans = new RandomListNode(pHead->label); 
        // 这个作为原链表的中间节点 
        RandomListNode* now = pHead;  
        // 这个作为最终节点的中间节点
        RandomListNode* head = ans;  
        map<RandomListNode*,RandomListNode*> mp;
        // 先预处理一边记录每个节点的信息
        while(now){  
            mp[now]=new RandomListNode(now->label);
            now=now->next;
        }
        now=pHead;
        // 构造出最终的链表
        while(now){ 
            head->next=mp[now->next];
            head->random=mp[now->random];
            head=head->next;
            now=now->next;
        }
        return ans;
    }
};

解法二

• 上面的一种写法是先将每个节点都存储完，然后再进行一次遍历。但是我们发现，其实也可以一边将节点存入map，一边构造出新的链表。每次我们看map里面是否存在我们需要的节点，如果存在，直接用即可。如果不存在，那么说明我们需要new出一个新的节点。这里要注意的是由于next可以保证不为NULL，但是random指针我们不能确定在什么时候为NULL，所以我们需要加一个额外的判断。

• 具体请看代码

class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead) {
        // 先判断是否为空
        if(pHead==NULL){  
            return NULL;
        }
        // new出最终的头节点
        RandomListNode* ans = new RandomListNode(pHead->label);  
        // 这个作为最终节点的中间节点
        RandomListNode* head = ans;  
        map<RandomListNode*,RandomListNode*> mp;
        mp[pHead]=head;
        while(pHead->next){  
            RandomListNode* now=head;
            if(!mp[pHead->next]){
                // 判断下一个节点对应的新节点是否存在
                // 如果不存在，就new一个出来
                now=new RandomListNode(pHead->next->label);
            }else{
                now=mp[pHead->next];
            }
            head->next=now;
            if(!mp[pHead->random]){
                // 判断random指针对应的新节点是否存在，
                // 如果不存在，需要加一个判断是否为NULL，
                // 不为NULL那么就可以new出来
                RandomListNode* r = pHead->random==NULL?NULL:
                    new RandomListNode(pHead->random->label);
                head->random=r;
                mp[pHead->random]=r;
            }else{
                head->random=mp[pHead->random];
            }
            head=head->next;
            pHead=pHead->next;
        }
        head->random=mp[pHead->random];
        return ans;
    }
};