双指针法

双指针法一

• 克隆节点在原节点后，遍历链表构建随机映射关系，拆分节点。
• 新链表的随机节点可以通过原链表随机关系获得。
• 核心：new_cur->random=cur->random->next。
• 时间/空间: O(n)/O(n)

#include <cstdlib>
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead) {
        if(!pHead) return nullptr;
        RandomListNode* cur=pHead;
        //克隆节点
        while(cur)
        {
            RandomListNode* next=new RandomListNode(cur->label);
            next->next=cur->next;
            cur->next=next;
            cur=cur->next->next;
        }
        //连接random节点
        RandomListNode* ret=pHead->next,*cur1=pHead->next;
        cur=pHead;
        while(cur)
        {
            cur1->random=cur->random?cur->random->next:nullptr;
            cur=cur->next->next;
            if(cur1->next)
            cur1=cur1->next->next;
        }
        //拆分链表
        cur=pHead;
        cur1=ret;
        while(cur)
        {
            cur->next=cur->next->next;
            cur1->next=cur1->next?cur1->next->next:nullptr;
            if(cur) cur=cur->next;
            if(cur1) cur1=cur1->next; 

        }
        return ret;
    }
};

双指针法2

• 先复制链表，再链接随机节点
• 利用随机节点间在两个链表具有相同的相对距离关系，用双指针计算出相对距离
• 时间/空间： O(n^2)/O（n)

/*
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* cur=pHead;
        RandomListNode* new_head=new RandomListNode(pHead->label);
        cur=cur->next;
        RandomListNode* new_cur=new_head;
        while(cur)//cur存在
        {
            new_cur->next=new RandomListNode(cur->label);
            cur=cur->next;
            new_cur=new_cur->next;
        }
        new_cur->next=cur;//nullptr;
        // Random
        cur=pHead;
        new_cur=new_head;
        while(cur)
        {   RandomListNode* cur2=pHead;
            int step=0;
            while(cur2!=cur->random)
            {
                cur2=cur2->next;
                step+=1;
            }
            RandomListNode* new_cur2=new_head;
            while(step)
            {
                new_cur2=new_cur2->next;
                step--;
            }
            new_cur->random=new_cur2;
            cur=cur->next;
            new_cur=new_cur->next;
        }
        return new_head;
    }
};

哈希法

• 通过哈希保存映射关系。
• 注意遍历哈希的语法糖。
• 构建链表的cur节点，比原节点位置慢1个。
• 时间/空间: O(n)/O(n)。

class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead) {
        //哈希法
        if(!pHead)
        {
            return nullptr;
        }
        RandomListNode* dumpy=new RandomListNode(-1);
        RandomListNode* cur=pHead;
        RandomListNode* new_cur=dumpy;
        unordered_map<RandomListNode*, RandomListNode*> mp;
        while(cur)
        {
            RandomListNode* next=new RandomListNode(cur->label);
            new_cur->next=next;
            mp[cur]=new_cur->next;
            cur=cur->next;
            new_cur=new_cur->next;
        }//cur为空

        for(auto& [key,value]:mp)
        {
            value->random=!key->random?nullptr:mp[key->random];
        }
        delete dumpy;
        return mp[pHead];
    }
};