138. 复制带随机指针的链表

news/2025/2/18 11:24:12/

给你一个长度为 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]]
 public Node copyRandomList(Node head) {if (head == null) {return null;}Node cur = head;Map<Node, Node> map = new HashMap<>();while (cur != null) {map.put(cur, new Node(cur.val));cur = cur.next;}cur = head;while (cur != null) {map.get(cur).next = map.get(cur.next);map.get(cur).random = map.get(cur.random);cur = cur.next;}return map.get(head);}


http://www.ppmy.cn/news/46962.html

相关文章

【牛客网】树根与星际密码

目录 一、编程题 1.树根 2.星际密码 二、选择题 一、编程题 1.树根 链接&#xff1a;数根__牛客网 (nowcoder.com) 数根可以通过把一个数的各个位上的数字加起来得到。如果得到的数是一位数&#xff0c;那么这个数就是数根&#xff1b;如果结果是两位数或者包括更多位的数…

换个角度使用Redis去解决跨域存取Session问题

系列文章目录 Redis缓存穿透、击穿、雪崩问题及解决方法 Spring Cache的使用–快速上手篇 分页查询–Java项目实战篇 全局异常处理–Java实战项目篇 该系列文章持续更新&#xff0c;更多的文章请点击我的主页查看哦&#xff01; 文章目录 系列文章目录前言一、遇到的情况二、解…

【论文总结】V-Shuttle:可扩展和语义感知的 Hypervisor 虚拟设备模糊测试

介绍 这是来自2021 CCS的一篇论文&#xff0c;作者有GaoningPan, Xingwei Lin, Xuhong Zhang, Yongkang Jia, Shouling Ji, Chunming Wu, Xinlei Ying, Jiashui Wang, Yanjun Wu。该论文提出V-shuttle的新框架来执行管控程序的模糊测试&#xff0c;该框架执行可扩展和语义感知…

AVL树(C++实现)

文章目录 AVL树的概念AVL树结点定义AVL树的插入AVL树的旋转左单旋右单旋左右单旋右左双旋 AVL树的验证AVL树的性能AVL树及测试完整代码 AVL树的概念 二叉搜索树虽然可以缩短查找的效率,但如果数据有序或接近有序,那么二叉搜索树将退化为单支树,查找元素则相当于在顺序表中搜索…

WHOIS查询参考:域名注册信息的含义

以下详细说明了域名的域名所有者、管理联系人、技术联系人、付费联系人等信息的中英文含义。为注册域名和whois查询提供参考。 域名所有者注册信息含义 域名所有者&#xff08;Registrant&#xff09;是指域名属于谁&#xff0c;用于判定域名所有权。域名所有者可以是单位企业…

C语言实现顺序表--数据结构

魔王的介绍&#xff1a;&#x1f636;‍&#x1f32b;️一名双非本科大一小白。魔王的目标&#xff1a;&#x1f92f;努力赶上周围卷王的脚步。魔王的主页&#xff1a;&#x1f525;&#x1f525;&#x1f525;大魔王.&#x1f525;&#x1f525;&#x1f525; ❤️‍&#x1…

如何使用Tensorflow神经网络模型来完成兰州房价预测分析?

兰州房价预测是一个非常热门的话题,许多人都对如何预测兰州房价感兴趣。在本文中,我将介绍如何使用TensorFlow来预测兰州房价,并提供Python源代码。 首先,我们需要收集兰州的房价数据。我们可以从房地产网站或政府统计数据中获取。在本文中,我们将使用Kaggle上提供的兰州…

收音机知识,调谐(选频/滤波),调制(升频)

参考&#xff1a;https://www.bilibili.com/video/BV1d14y1N7nm/?spm_id_from333.999.0.0&vd_source00bd76f9d6dc090461cddd9f0deb2d51 有关知识提纲 整个信号的传输变化调谐人耳听到声音的频率范围&#xff08;20~20000Hz&#xff09;天线和传送信号的波长关系波长和天线…