复杂链表的复制

一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head

方法一:用unordered_map,key为原链表的每一个节点,value为对应节点的复制,
步骤:
1.遍历链表,对于每一个节点,复制一个一样的(只管值相同,先不管指针域)用RandomListNode* temp=new RandomListNode(p->label);进行复制
2.再次遍历链表,对于每一个节点的next和random都可以去找map里的节点给我的节点加上去:m[p]->next=m[p->next]

/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead)
    {
        unordered_map<RandomListNode*,RandomListNode*> m;
        RandomListNode* p=pHead;
        while(p!=NULL)
        {
            RandomListNode* temp=new RandomListNode(p->label);//RandomListNode* temp=NULL;
            m.insert(make_pair(p,temp));                   //temp->label=p->label;一开始用这两行,本机可以,但是牛客报错
            p=p->next;
        }
        p=pHead;
        while(p!=NULL)
        {
            m[p]->next=m[p->next];
            m[p]->random=m[p->random];
            p=p->next;
        }
        return m[pHead];
    }
};

方法2:把每个节点复制,复制后的点挂在节点后面:1->1'->2->2'->3->3',然后再进行分离
代码比较复杂,尝试过,本机可以但是牛客报错了

全部评论

相关推荐

07-02 18:09
门头沟学院 Java
苍穹外卖和谷粒商城这俩是不是烂大街了,还能做吗?
想去重庆的鸽子在吐槽:你不如把这俩做完自己搞明白再优化点再来问 何必贩卖焦虑
点赞 评论 收藏
分享
程序员饺子:正常 我沟通了200多个 15个要简历 面试2个 全投的成都的小厂。很多看我是27直接不会了😅
点赞 评论 收藏
分享
小浪_Coding:找硬件测试,也可兼顾软测欧, 简历还可以的 ,注意排版,项目写的有条理一点, 然后个人技能多加点, 润色好简历之后就开始沟通海投了,深圳,东莞这边做硬件相关的公司还不少, 医疗类,仪器类的都可以尝试
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-01 11:47
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务