剑指 Offer 35. 复杂链表的复制
题目
题目链接
https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/
解题思路
题目理解
首先要理解题目意思
题目要求复制一份新的链表
意思链表点节点都必须是新生成的节点,且要求保证链表的关系不变
不是让你直接 return head 完事
输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
第一个节点的 val = 7,random 为 null
第二个节点的 val = 13,random 指向链表的第1个节点,也就是指向 [7, null] 节点
第三个节点的 val = 11,random 指向链表的第5个节点,也就是指向 [1,0] 节点
第四个节点的 val = 10,random 指向链表的第3个节点,也就是指向 [11,4] 节点
第五个节点的 val = 1,random 指向链表的第1个节点,也就是指向 [7, null] 节点
PS:节点的 val 是会重复的
解题思路
其实这个题目的难点就在于 random 字段
random 字段可能指向自己前面的节点,可能指向自己,也可能指向自己后面还没生成的节点
假如 random 指向了后面的节点,我们可以 new 出节点没问题,但是后面递归到这个节点时候就要能直接拿到之前已经 new 出的节点
因此我这里我用一个 HashMap 来存储已经生成的节点
每生成一个节点就加入到 HashMap 中
后续不管是迭代到的节点,或者是 random 的节点都优先去 HashMap 中找
找的到直接拿出来,找不到就生成一个新的再放进去
HashMap 的 Key 用旧链表的节点来存储,因为 val 是可能重复的
具体代码
/*
// 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) {
// head 空判断
if (head == null) {
return null;
}
// 临时缓存 HashMap,key 旧节点,value 新生成的对应节点
Map<Node, Node> tmp = new HashMap<>();
Node headNode = null, parentNode = null, curNode;
while (head != null) {
// 如果节点已经生成过,就直接从缓存中拿出
if (tmp.containsKey(head)) {
curNode = tmp.get(head);
} else {
// 没生成过,new 个新的
curNode = new Node(head.val);
// 节点入临时缓存
tmp.put(head, curNode);
}
// 判断是否是首节点
if (headNode == null) {
// 设置头节点
headNode = curNode;
} else {
// 将上个节点的 next 指向当前节点
parentNode.next = curNode;
}
// next 节点尝试从缓存中取,找不到就生成一个新的放进去
if (head.next != null) {
if (!tmp.containsKey(head.next)) {
tmp.put(head.next, new Node(head.next.val));
}
curNode.next = tmp.get(head.next);
}
// random 节点尝试从缓存中取,找不到就生成一个新的放进去
if (head.random != null) {
if (!tmp.containsKey(head.random)) {
tmp.put(head.random, new Node(head.random.val));
}
curNode.random = tmp.get(head.random);
}
// 指向下个节点
head = head.next;
// 当前节点变为上个节点
parentNode = curNode;
}
return headNode;
}
}
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgagffa
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01