题目描述

示例

思路一：哈希表

c++中stl的哈希表相关知识见c++STL哈希表

• 假如链表没有随机指针, 我们的拷贝方式很简单, 只要先创建一个哨兵节点, 然后遍历一下给定链表, 创建新节点, 并不断和上个节点连接。
• 本题的难点就在于每个节点还有一个指向空或其它节点的指针, 一种比较直观的想法就是先把整条链表连起来, 然后再挨着改变指针, 因此我们可以用哈希表来存放指针的映射关系, 然后根据将随机指针指向原链表随机指针映射在新链表的位置。
• 算法实现：首先创建一个哨兵节点, 遍历一次原链表, 先将除随机指针外的部分创建并连接, 同时用哈希表记录指针之间的映射,最后遍历一次哈希表, 将随机指针指向对应的位置。

代码

class Solution {
public:
RandomListNode* Clone(RandomListNode* pHead) {
    if(!pHead) return pHead;    // 为空则直接返回空
    unordered_map<RandomListNode*, RandomListNode*> mp;    // 创建哈希表

    RandomListNode* dummy = new RandomListNode(0);    // 哨兵节点

    RandomListNode *pre = dummy, *cur = pHead;    // 指向哨兵和链表头的指针

    while(cur){
        RandomListNode* clone = new RandomListNode(cur->label);    // 拷贝节点
        pre->next = clone;    // 与上个结点连接
        mp[cur] = clone;    // 记录映射关系
        pre = pre->next;    // 指针移动
        cur = cur->next;
    }

    for(auto& [key, value] : mp){    // 遍历哈希表
        value->random = key->random == NULL ? NULL : mp[key->random];
    }

    delete dummy;    // 释放哨兵节点空间
    return mp[pHead];
}
};

思路二：链表拼接、拆分

• 将原链表的结点对应的拷贝节点连在其后, 最后链表变成 原1 -> 拷1 -> 原2 -> 拷2 -> ... -> null 的形式。
• 然后我们再逐步处理对应的随机指针, 使用双指针, 一个指针指向原链表的节点, 一个指向拷贝链表的节点, 那么就有 拷->random = 原->random->next (random不为空)。
• 最后再用双指针将两条链表拆分即可, 此算法大大优化了空间复杂度, 十分优秀。

代码一

class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead) {
        if(!pHead) return pHead;    // 为空则返回
        RandomListNode* cur = pHead;
        while(cur){
            RandomListNode* tmp = new RandomListNode(cur->label);    // 拷贝节点
            tmp->next = cur->next;
            cur->next = tmp;
            cur = tmp->next;
        }

        RandomListNode *old = pHead, *clone = pHead->next, *ret = pHead->next;
        while(old){
            clone->random = old->random == NULL ? NULL : old->random->next;    // 处理拷贝节点的随机指针
            if(old->next) old = old->next->next;    // 注意特判空指针
            if(clone->next) clone = clone->next->next;
        }

        old = pHead, clone = pHead->next;
        while(old){    // 拆分链表
            if(old->next) old->next = old->next->next;
            if(clone->next) clone->next = clone->next->next;
            old = old->next;
            clone = clone->next;
        }

        return ret;
    }
};

代码二

/*

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) return nullptr;
        RandomListNode* root=new RandomListNode(pHead->label);
        RandomListNode * next=root;
        RandomListNode * copy=nullptr;
        RandomListNode* cur=pHead;
        while(cur->next!=nullptr) 
        {
             cur=cur->next;
             RandomListNode * copy=new RandomListNode(cur->label);          
             next->next=copy;
             next=copy;           
        }
        next->next=nullptr;
        next=root;
        cur=pHead;  //记录原list的位置
        RandomListNode* next2=root;   //记录新list当前位置
        RandomListNode* cur2=pHead;     //记录原list当前位置
        while(next!=nullptr)
        {
            if(cur->random){
                while(next2->label!=cur->random->label)
                {
                    next2=next2->next;
                }
               next->random=next2;
            }        
          next=next->next;
          next2=root; 
          cur=cur->next;
          cur2=pHead;
        }
         return root;

}
    };