Leetcode 138 Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

复制一个带有随机后续节点的链表,

因为随机后续节点可能在复制到当前结点时还没有被创建出来,所以需要保存新节点和老节点之间的对应关系。

当然也有人通过在老节点后插入新节点的方法完成,这样的好处是空间复杂度降低了,但坏处是实现起来麻烦一些,而且如果链表中有环,这样的方法将失效。

/**
 * 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*> mp;
        if(!head) return NULL;
        RandomListNode* p = head;
        RandomListNode* res = new RandomListNode(head->label);
        RandomListNode* q = res;
        mp[p] = q;
        while(p->next)
        {
            p = p->next;
            q->next = new RandomListNode(p->label);
            q = q->next;
            mp[p] = q;
        }
        p = head;
        q = res;
        while(p)
        {
            q->random = mp[p->random];
            p = p->next;
            q = q->next;
        }
        return res;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏增长技术

ConcurrentModificationException

12630
来自专栏C#

解析.NET对象的跨应用程序域访问(上篇)

   在目前的项目开发中,分布式开发已经逐渐成为主流。一个项目要是没有采用分布式架构,都不好意思跟别人说这是一个完整的项目。这句话虽然有些过激,但是随着人们对效...

22750
来自专栏遊俠扎彪

C语言C99标准中的变长数组(VLA)

长期以来,我都很自然的认为定义和声明数组时,数组大小必须是一个常量表达式,因为刚学编程的时候在这个上面翻过好多次语法错误。那个时候大致会写如下的代码:

48190
来自专栏Dawnzhang的开发者手册

数据结构与算法学习笔记之 提高读取性能的链表(上)

链表(Linked list)比数组稍微复杂一点,在我们生活中用到最常见的应该是缓存,它是一种提高数据读取性能的技术,常见的如cpu缓存,浏览器缓存,数据库缓...

12730
来自专栏奔跑的蛙牛技术博客

利用接口集合实现简单算法

13430
来自专栏xingoo, 一个梦想做发明家的程序员

函数声明后面的const用法

void function() const{} 通常我们会看到一些函数声明后面会跟着一个const,这个const是做什么的呢? 看一下下面的例子,就知道了。直...

22150
来自专栏Java技术栈

干货:排名前 16 的 Java 工具类!

在Java中,工具类定义了一组公共方法,这篇文章将介绍Java中使用最频繁及最通用的Java工具类。以下工具类、方法按使用流行度排名,参考数据来源于Github...

54150
来自专栏xiaoxi666的专栏

二分查找变种

该算法有很多版本,这里给出java中实现比较好的一种方式。其中,>>>为无符号右移。

14320
来自专栏微信公众号:Java团长

Java开发中对Redis的基本操作总结

想要在 Java 中使用 Redis,我们首先需要安装 redis 服务及 Java redis 驱动。

3.9K50
来自专栏程序员互动联盟

【编程基础第十一讲】代码如何写才最漂亮第一篇

存在问题: 好多小伙伴对编码的格式作用模糊,以为只要完成功能就行,其实这种观点是错误的,一定要重视代码规范,不然你哭的地都找不到。 如何实施: 良好的代码开发习...

28470

扫码关注云+社区

领取腾讯云代金券