lintcode105. 複制帶随機指針的連結清單

給出一個連結清單，每個節點包含一個額外增加的随機指針可以指向連結清單中的任何節點或空的節點。

傳回一個深拷貝的連結清單。

思路：做完克隆圖才做的這個，直接按克隆圖的做法做了

https://blog.csdn.net/weixin_43981315/article/details/104299101

/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    /**
     * @param head: The head of linked list with a random pointer.
     * @return: A new head of a deep copy of the list.
     */
    RandomListNode *copyRandomList(RandomListNode *head) {
        // write your code here
        if(head==NULL) return NULL;
        map<RandomListNode*,RandomListNode*> compare;
        queue<RandomListNode*> q;
        set<RandomListNode*>judge;
        q.push(head);
        RandomListNode*newhead=new RandomListNode(head->label);
        compare[head]=newhead;
        while(!q.empty())
        {
            RandomListNode*cur=q.front();
            q.pop();
            if(!judge.count(cur))
            {
                judge.insert(cur);
                RandomListNode*copy=compare[cur];
                if(cur->next==NULL) copy->next=NULL;//注意檢查是不是NULL
                else if(compare.find(cur->next)!=compare.end())
                {
                    copy->next=compare[cur->next];
                }
                else
                {
                    RandomListNode*cnext=new RandomListNode(cur->next->label);
                    copy->next=cnext;
                    q.push(cur->next);
                    compare[cur->next]=cnext;
                }
                if(cur->random==NULL) copy->random=NULL;
                else if(compare.find(cur->random)!=compare.end())
                {
                    copy->random=compare[cur->random];
                }
                else
                {
                    RandomListNode*crandom=new RandomListNode(cur->random->label);
                    copy->random=crandom;
                    q.push(cur->random);
                    compare[cur->random]=crandom;
                }
            }
        }
        return newhead;
    }
};
           

網上看到的更簡潔的做法

/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead)
    {
        map<RandomListNode*,RandomListNode*>temp;
        RandomListNode*s=new RandomListNode(0);
        RandomListNode*head=s;
        RandomListNode*cur=pHead;
        //複制結點值和next關系
        while(cur!=NULL)
        {
          RandomListNode*newnode=new RandomListNode(cur->label);
            temp[cur]=newnode;//原連結清單結點對應的複制連結清單結點,關鍵點所在
            s->next=newnode;
            s=s->next;
            cur=cur->next;
        }
        cur=pHead;//複制随機指針 
        while(cur!=NULL)
        {
            temp[cur]->random=temp[cur->random];//即newnode->random=temp[cur->random],關鍵點所在
            cur=cur->next;
        }
        return head->next;
   }
   原文連結：https://blog.csdn.net/weixin_41413441/article/details/79097261
};