IT源码网

复杂链表的复制讲解

developer 2020年10月21日 编程语言 281 0

题目描述

输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针random指向一个随机节点),请对此链表进行深拷贝,并返回拷贝后的头结点。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)
 
解:复制一个节点,并用map跟原节点关联起来
/* 
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==nullptr) 
        { 
            return nullptr; 
        } 
 
        RandomListNode *p1=pHead; 
        RandomListNode *p2=pHead; 
 
        map<RandomListNode *,RandomListNode *> node_map; 
        while (p1!=nullptr) { 
            RandomListNode *tmp=new RandomListNode(p1->label); 
            node_map[p1]=tmp; 
            p1=p1->next; 
        } 
 
        while(p2!=nullptr) 
        { 
            if(p2->next!=nullptr) 
            { 
                node_map[p2]->next=node_map[p2->next]; 
            } 
            else 
            { 
                node_map[p2]->next=nullptr; 
            } 
            node_map[p2]->random=node_map[p2->random]; 
            p2=p2->next; 
             
        } 
        return node_map[pHead]; 
    } 
};

 

发布评论
IT源码网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

设计跳表讲解
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。