【leetcode100】随机链表的复制

devtools/2025/1/14 23:33:18/

1、题目描述


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

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

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

返回复制链表的头节点。

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

你的代码 只 接受原链表的头节点 head 作为传入参数。

示例 1:

输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]

2、初始思路

2.1 思路

创建新节点,将原节点的值赋值后保存在字典中,然后使用get获取存取的值。

"""
# Definition for a Node.
class Node:def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):self.val = int(x)self.next = nextself.random = random
"""class Solution:def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':if not head:return dic = {}cur = headwhile cur:#创建了一个新的节点,新节点的值与原节点 cur 的值相同。dic[cur] = Node(cur.val)cur = cur.nextcur = headwhile cur:dic[cur].next = dic.get(cur.next)dic[cur].random = dic.get(cur.random)cur = cur.nextreturn dic[head]

文章来源:https://blog.csdn.net/qq_65509025/article/details/144609018
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.ppmy.cn/devtools/144836.html

相关文章

【Leetcode 热题 100】105. 从前序与中序遍历序列构造二叉树

问题背景 给定两个整数数组 p r e o r d e r preorder preorder 和 i n o r d e r inorder inorder,其中 p r e o r d e r preorder preorder 是二叉树的 先序遍历, i n o r d e r inorder inorder 是同一棵树的 中序遍历,请构造二叉树并…

【JAVA】JAVA接口公共返回体ResponseData封装

一、JAVA接口公共返回体ResponseData封装&#xff0c;使用泛型的经典 例子 public class ResponseData<T> implements Serializable { /** * */ private static final long serialVersionUID 7098362967623367826L; /** * 响应状态码 */ …

基于 SSM 和 Vue 架构的新锐台球厅管理系统:创新设计引领高效实现

1系统概述 1.1 研究背景 如今互联网高速发展&#xff0c;网络遍布全球&#xff0c;通过互联网发布的消息能快而方便的传播到世界每个角落&#xff0c;并且互联网上能传播的信息也很广&#xff0c;比如文字、图片、声音、视频等。从而&#xff0c;这种种好处使得互联网成了信息传…

贪心算法 greedy

文章目录 参考贪心算法[Leetcode455 分发饼干](https://leetcode.cn/problems/assign-cookies/description/)分析题解 [Leetcode135 分发糖果](https://leetcode.cn/problems/assign-cookies/description/)分析题解 leetcode435无重叠区间分析题解 参考 https://github.com/ch…

ElasticSearch08-分析器详解

零、文章目录 ElasticSearch08-分析器详解 1、分析器原理 Elasticsearch的分词器&#xff08;Analyzer&#xff09;是全文搜索的核心组件&#xff0c;它负责将文本转换为一系列单词&#xff08;term/token&#xff09;的过程&#xff0c;也叫分词。 &#xff08;1&#xff…

Windows系统如何配置远程音频

场景 RemoteFx 是 Windows RDP 桌面协议升级版&#xff0c;RDP 8.0起可以使用 RemoteFx 来使用 USB 重定向&#xff0c;将本地 USB 设备通过 RDP 的数据通道重定向到远程桌面&#xff0c;解决云端机器无法使用 USB 设备的问题。 客户端&#xff1a;Windows 10 操作系统 服务…

使用ElasticSearch实现全文检索

文章目录 全文检索任务描述技术难点任务目标实现过程1. java读取Json文件&#xff0c;并导入MySQL数据库中2. 利用Logstah完成MySQL到ES的数据同步3. 开始编写功能接口3.1 全文检索接口3.2 查询详情 4. 前端调用 全文检索 任务描述 在获取到数据之后如何在ES中进行数据建模&a…

PostgreSQL表达式的类型

PostgreSQL表达式是数据库查询中非常重要的组成部分&#xff0c;它们由一个或多个值、运算符和PostgreSQL函数组合而成&#xff0c;用于计算出一个单一的结果。这些表达式类似于公式&#xff0c;可以用查询语言编写&#xff0c;并用于查询数据库中的特定数据集。 PostgreSQL表…