复杂链表的复制

一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的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',然后再进行分离
代码比较复杂,尝试过,本机可以但是牛客报错了

全部评论

相关推荐

人力小鱼姐:实习经历没有什么含金量,咖啡店员迎宾这种就别写了,其他两段包装一下 想找人力相关的话,总结一下个人优势,结合校园经历里有相关性的部分,加一段自我评价
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
05-29 20:12
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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