lintcode105. 复制带随机指针的链表

秒速五厘米 2023-07-05 11:49 16阅读 0赞

给出一个链表，每个节点包含一个额外增加的随机指针可以指向链表中的任何节点或空的节点。  
返回一个深拷贝的链表。

思路：做完克隆图才做的这个，直接按克隆图的做法做了  
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
    };