另一种方法(C++)

复杂链表的复制

http://www.nowcoder.com/questionTerminal/f836b2c43afc4b35ad6adc41ec941dba

/*
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)//判断头指针为空
return pHead;
RandomListNode* res = new RandomListNode(-1);//创建新头指针

    RandomListNode* ph = pHead;
    map<RandomListNode*,int> m1;//记录旧链表地址映射关系
    map<int,RandomListNode*> m2;//记录新链表地址映射关系
    RandomListNode* cur;
    RandomListNode* head = res;
    int i = 0;
    while(pHead){//复制主体链表
        cur = new RandomListNode(-1);
        cur->label = pHead->label;
        m1[pHead]=i;
        m2[i]=cur;
        ++i;
        head->next=cur;
        head = head->next;
        pHead = pHead->next;
    }
    head->next = nullptr;
    for(int j=0;j<i;++j){//添加随机指针部分
        if(!ph->random)
            m2[j]->random=nullptr;
        else{
            int index = m1.find(ph->random)->second;
            m2[j]->random=m2[index];
        }
        ph=ph->next;
    }
    return res->next;
}

};

全部评论

相关推荐

八股刚起步,看了javaguide,小林coding,还有面渣,感觉面渣是体验最好的,请问只看面渣够用吗,有不完善的需要补吗?
码农索隆:先背最基础的知识,然后理解情景题,现在面试大多数喜欢问情景题,更考验面试者的基础和临场发挥情况
点赞 评论 收藏
分享
zYvv:双一流加大加粗再标红,然后广投。主要是获奖荣誉不够,建议开始不用追求大厂,去别的厂子刷下实习。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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