复杂链表的复制解析

熊孩纸 阅读:390 2020-10-21 17:08:27 评论: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]; 
    } 
};

 

声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

发表评论
搜索
排行榜
KIKK导航

KIKK导航

关注我们