力扣热题100_链表_138_随机链表的复制

文章目录

  • 题目链接
  • 解题思路
  • 解题代码


题目链接

138. 随机链表的复制
给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如,如果原链表中有 X 和 Y 两个节点,其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ,同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示:

val:一个表示 Node.val 的整数。
random_index:随机指针指向的节点索引(范围从 0 到 n-1);如果不指向任何节点,则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。

示例 1:
在这里插入图片描述
输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2:
在这里插入图片描述
输入:head = [[1,1],[2,1]]
输出:[[1,1],[2,1]]

示例 3:
在这里插入图片描述

输入:head = [[3,null],[3,0],[3,null]]
输出:[[3,null],[3,0],[3,null]]

解题思路

解法迭代
1.遍历链表,利用哈希表,以旧节点:新节点为映射关系,将节点关系存储下来
2.再次遍历链表,将新链表的 next 和 random 指针设置好

解题代码

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head:
            return None
        node_dict = dict()
        curr = head
        while curr:
            new_node = Node(curr.val, None, None)
            node_dict[curr] = new_node
            curr = curr.next
        curr = head
        while curr:
            if curr.next:
                node_dict[curr].next = node_dict[curr.next]
            if curr.random:
                node_dict[curr].random = node_dict[curr.random]
            curr = curr.next
        return node_dict[head]

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/521931.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

事件时间+时间窗口,最后一个窗口不执行问题踩坑与源码分析

事件时间时间窗口,最后一个窗口不执行问题踩坑与源码分析 1. 结论 在使用事件时间和时间窗口的过程中,当最后一个事件的事件时间未达到时间窗口的最大时间,窗口不会触发。 举例说明,在按小时的滚动窗口中,假设当前时…

开启虚拟机时出现此主机支持 Intel VT-x,但 Intel VT-x 处于禁用状态怎么解决

问题描述 虚拟机安装完成后,点击开启此虚拟机弹出系统提示 原因分析: Intel VT-x 处于禁用状态,需要开启。 解决方案: 以联系小新笔记本电脑为例,进入BIOS界面,将Intel Virtual Technology设置成Enabl…

STL--迭代器的介绍

一.迭代器介绍🍗 迭代器是 C 标准模板库(STL)中的一个重要概念。简单来说,迭代器就像是一个指针,用于访问和遍历容器中的元素(比如数组、链表、集合等)。迭代器提供了一种统一的方法来访问容器…

力扣1448---统计二叉树中好节点的数量(Java、DFS、中等题)

题目描述: 给你一棵根为 root 的二叉树,请你返回二叉树中好节点的数目。 「好节点」X 定义为:从根到该节点 X 所经过的节点中,没有任何节点的值大于 X 的值。 示例 1: 输入:root [3,1,4,3,null,1,5] 输出…

开启新纪元中凡工业装备邀您参观2024第13届生物发酵展

参展企业介绍 中凡工业是一家专注于螺旋板式换热器以及相关非标设备制造的生产厂家。公司产品主要应用于环保废水、污水处理、可再生能源、食品、药化、焦化、农化、精细化工等行业,为这些行业解决生产工艺中的液体加热,液体冷却,气体冷凝&a…

聚观早报 | 沃尔沃发布一季度全球销量;苹果将举办财报电话会议

聚观早报每日整理最值得关注的行业重点事件,帮助大家及时了解最新行业动态,每日读报,就读聚观365资讯简报。 整理丨Cutie 4月07日消息 沃尔沃发布一季度全球销量 苹果将举办新财报电话会议 荣耀Magic6支持5.5G通信 特斯拉将建最大超级充…

Word技巧之【允许修改受保护文档的部分内容】

给Word文档设置“限制编辑”,可以保护文档不能随意编辑更改,但如果文档中有部分内容,是需要供打开文档的人可以修改,要怎么使这部分内容允许修改呢?下面一起来看看,如何设置Word文档中允许部分内容可修改。…

政安晨:【深度学习神经网络基础】(三)—— 激活函数

目录 线性激活函数 阶跃激活函数 S型激活函数 双曲正切激活函数 修正线性单元 Softmax激活函数 偏置扮演什么角色? 政安晨的个人主页:政安晨 欢迎 👍点赞✍评论⭐收藏 收录专栏: 政安晨的机器学习笔记 希望政安晨的博客能够对您有所裨…

Java Spring IoCDI :探索Java Spring中控制反转和依赖注入的威力,增强灵活性和可维护性

💓 博客主页:从零开始的-CodeNinja之路 ⏩ 收录文章:Java Spring IoC&DI :探索Java Spring中控制反转和依赖注入的威力,增强灵活性和可维护性 🎉欢迎大家点赞👍评论📝收藏⭐文章 目录 前提小知识:高内…

12-2-CSS 字体图标

个人主页:学习前端的小z 个人专栏:HTML5和CSS3悦读 本专栏旨在分享记录每日学习的前端知识和学习笔记的归纳总结,欢迎大家在评论区交流讨论! 文章目录 CSS 字体图标1 字体图标的产生2 字体图标的优点3 字体图标的下载4 字体图标的…

LangChain-10(2) 加餐 编写Agent获取本地Docker运行情况 无技术含量只是思路

可以先查看 上一节内容,会对本节有更好的理解。 安装依赖 pip install langchainhub编写代码 核心代码 tool def get_docker_info(docker_name: str) -> str:"""Get information about a docker pod container info."""result…

隐私计算实训营学习八:隐语SCQL的开发实践

文章目录 一、SCQL使用集成最佳实践1.1 SCQL使用流程1.2 SCQL部署1.3 SCQL使用示例 二、SCQL工作原理三、使用SecretNote上手体验SCQL 一、SCQL使用集成最佳实践 1.1 SCQL使用流程 SCQL使用: SCQL 开放 API 供⽤户使⽤/集成。可以使⽤SCDBClient上⼿体验(类似与My…

归一化技术比较研究:Batch Norm, Layer Norm, Group Norm

归一化层是深度神经网络体系结构中的关键,在训练过程中确保各层的输入分布一致,这对于高效和稳定的学习至关重要。归一化技术的选择(Batch, Layer, GroupNormalization)会显著影响训练动态和最终的模型性能。每种技术的相对优势并…

CSS - 你实现过宽高自适应的正方形吗

难度 难度级别:中高级及以上 提问概率:80% 宽高自适应的需求并不少见,尤其是在当今流行的大屏系统开发中更是随处可见,很显然已经超越了我们日常将div写死100px这样的范畴,那么如何实现一个宽高自适应的正方形呢?这里提出两种实现方案。…

【Linux】进程初步理解

个人主页 : zxctscl 如有转载请先通知 文章目录 1. 冯诺依曼体系结构1.1 认识冯诺依曼体系结构1.2 存储金字塔 2. 操作系统2.1 概念2.2 结构2.3 操作系统的管理 3. 进程3.1 进程描述3.2 Linux下的PCB 4. task_struct本身内部属性4.1 启动4.2 进程的创建方式4.2.1 父…

JAVA:探索Apache POI 处理利器

请关注微信公众号:拾荒的小海螺 1、简述 Apache POI是Apache软件基金会的顶级项目之一,它允许Java开发人员读取和写入Microsoft Office格式的文档,包括Excel、Word和PowerPoint文件。通过POI,开发人员可以创建、修改和读取Excel…

面试(04)————JavaWeb

1、网络通讯部分 1.1、 TCP 与 UDP 区别? 1.2、什么是 HTTP 协议? 1.3、TCP 的三次握手,为什么? 1.4、HTTP 中重定向和请求转发的区别? 1.5、 Get 和 Post 的区别? 2、cookie 和 session 的区别&am…

加入酷开会员 酷开系统带你一起开启看电视的美好时光!

看电视对孩子和大人来说,都是有好处的。英国的《星期日泰晤士报》曾刊登报道:“看电视可以让小孩增长见闻,学习各种良好的社交和学习技巧,从而为他们今后的学习打下良好的基础。”而对于成年人来说,看电视也是一种娱乐…

linux 安装 pptp 协议

注意:目前iOS已不支持该协议 yum -y install ppp wget https://download-ib01.fedoraproject.org/pub/epel/7/x86_64/Packages/p/pptpd-1.4.0-2.el7.x86_64.rpm yum -y install pptpd-1.4.0-2.el7.x86_64.rpm vi /etc/pptpd.conf 去除 localip 和 remoteip的注释 …

【.Net】Polly

文章目录 概述服务熔断、服务降级、服务限流、流量削峰、错峰、服务雪崩Polly的基本使用超时策略悲观策略乐观策略 重试策略请求异常响应异常 降级策略熔断策略与策略包裹(多种策略组合) 参考 概述 Polly是一个被.NET基金会支持认可的框架,同…