LeetCode 138——复制带随机指针的链表

栏目: C · 发布时间: 7年前

内容简介:第一次遍历链表的时候,复制旧链表的节点值建立一个新的链表,同时定义一个 unordered_map 作为哈希表,哈希表的键为旧链表的节点指针,值为新链表的节点指针。然后,第二次遍历链表,访问旧链表节点的随机指针,然后以此为键从 map 中取出对应的新链表节点指针,这也就是当前新链表节点的随机指针。获取更多精彩,请关注「seniusen」!
LeetCode 138——复制带随机指针的链表

2. 解答

第一次遍历链表的时候,复制旧链表的节点值建立一个新的链表,同时定义一个 unordered_map 作为哈希表,哈希表的键为旧链表的节点指针,值为新链表的节点指针。

然后,第二次遍历链表,访问旧链表节点的随机指针,然后以此为键从 map 中取出对应的新链表节点指针,这也就是当前新链表节点的随机指针。

/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        
        unordered_map<RandomListNode *, RandomListNode *> nodemap;
        RandomListNode *temp = head;
        RandomListNode *new_head = new RandomListNode(0); //哨兵节点,方便操作
        RandomListNode *copy_temp = new_head;
 
        // 建立新链表
        while (temp)
        {
            copy_temp->next = new RandomListNode(temp->label);
            nodemap[temp] = copy_temp->next;
            
            temp = temp->next;
            copy_temp = copy_temp->next;
        }
        
        RandomListNode *random_temp = NULL;
        temp = head;
        copy_temp = new_head->next;
        // 填充新链表的随机指针
        while (temp)
        {
            random_temp = temp->random;
            if (random_temp != NULL)   copy_temp->random = nodemap[random_temp];
            else    
                copy_temp->random = NULL;
            
            temp = temp->next;
            copy_temp = copy_temp->next;
        }
        
        return new_head->next;
    }
};
复制代码

获取更多精彩,请关注「seniusen」!

LeetCode 138——复制带随机指针的链表

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

马云:未来已来

马云:未来已来

阿里巴巴集团 / 红旗出版社 / 2017-4-1 / CNY 49.00

阿里巴巴集团:全球主要的互联网公司之一,由马云带领其他17个创始人,于1999年在中国杭州创立。阿里巴巴集团经营多元化的互联网业务,以“让天下没有难做的生意”为使命,致力于为创业者和消费者提供全球化的商业平台,打造开放、协同、繁荣的电子商务生态系统。自成立以来,阿里巴巴集团建立了领先的消费者电子商务、网上支付、B2B网上交易市场及云计算业务,并积极开拓无线应用、手机操作系统和互联网电视等领域。一起来看看 《马云:未来已来》 这本书的介绍吧!

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

URL 编码/解码
URL 编码/解码

URL 编码/解码