当前位置:网站首页>《力扣刷题计划》复制带随机指针的链表
《力扣刷题计划》复制带随机指针的链表
2022-07-05 17:55:00 【是小鱼儿哈】
每一个结点有三个属性:
链表的样子大概是这样:
注意这里我们复制的结点是引用类型,即我们复制的不只是结点的地址,我们需要复制的是旧结点。
比如一个这样的原链表
我们的复制不是又生成一个和上面一模一样的链表出来,我们复制的是有着原来链表结构的新的链表
新的链表的每个结点所对应的值可能和原来链表的值相同,但next和random的肯定是不同的(但所对应的关系是相同的)
为了在新链表中持和原来链表中各个结点的对应关系,我们需要用Map来记录
比如上图中
代码展示:
/*
// Definition for a Node.
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
*/
class Solution {
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
Node cur = head;
Map<Node, Node> map = new HashMap<>(); // 如果用TreeMap里面放的元素一定是可比较的,只能用HashMap
// 构建新旧结点的键值对关系,旧结点是Key,新结点是Value
while (cur != null) {
Node tmp = new Node(cur.val); // 构造新结点tmp,旧结点是cur
map.put(cur, tmp);
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); // 我们要返回的是新结点的head---及key(head) 所对应的 value值是map.get(head)
}
}
边栏推荐
- Size_ T is unsigned
- Introduction to VC programming on "suggestions collection"
- Generate XML schema from class
- Unicode processing in response of flash interface
- LeetCode笔记:Weekly Contest 300
- 集群部署如何解决海量视频接入与大并发需求?
- ISPRS2022/云检测:Cloud detection with boundary nets基于边界网的云检测
- To solve the stubborn problem of Lake + warehouse hybrid architecture, xinghuan Technology launched an independent and controllable cloud native Lake warehouse integrated platform
- Crontab 日志:如何记录我的 Cron 脚本的输出
- Neural network self cognition model
猜你喜欢
使用QT遍历Json文档及搜索子对象
吳恩達團隊2022機器學習課程,來啦
职场进阶指南:大厂人必看书籍推荐
EPM related
第十届全球云计算大会 | 华云数据荣获“2013-2022十周年特别贡献奖”
ELK日志分析系统
Star ring technology data security management platform defender heavy release
GFS distributed file system
JVM第三话 -- JVM性能调优实战和高频面试题记录
Isprs2022 / Cloud Detection: Cloud Detection with Boundary nets Boundary Networks Based Cloud Detection
随机推荐
消除`if()else{ }`写法
小白入门NAS—快速搭建私有云教程系列(一)[通俗易懂]
模拟百囚徒问题
JVM third talk -- JVM performance tuning practice and high-frequency interview question record
How awesome is the architecture of "12306"?
检查命名空间和类
每日一练:关于日期的一系列
Introduction to Resampling
Penetrate the whole intranet through socks agent
Isprs2022 / Cloud Detection: Cloud Detection with Boundary nets Boundary Networks Based Cloud Detection
Disorganized series
从类生成XML架构
rsync
「运维有小邓」用于云应用程序的单点登录解决方案
GIMP 2.10教程「建议收藏」
小林coding的内存管理章节
[performance test] full link voltage test
What are the changes in the 2022 PMP Exam?
Cmake tutorial step1 (basic starting point)
Sophon base 3.1 launched mlops function to provide wings for the operation of enterprise AI capabilities