每日leetcode——138. 复制带随机指针的链表
题目
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
【每日leetcode——138. 复制带随机指针的链表】例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
返回复制链表的头节点。
文章图片
思路
感觉这道题的难点，在于读懂题目说的啥...
其实题目的意思就是：
有一个链表，这个链表的节点，不光有next指针，还有一个random指针，随机指向某个节点或是None。现在让你复制一份这个链表。
def copyRandomList(head):
if not head:
return None# 设置一个字典
dic = {}
# 头节点处初始化一个指针cur
cur = head
# 第1遍遍历链表的每个节点
while cur!=None:
# 当前节点作为key，当前节点的copy节点作为val，存入字典中
dic[cur] = Node(cur.val)
# 移动指针，继续下一个节点
cur = cur.next# 第1遍遍历完成后，每个节点都复制了一份
# cur再放回到表头处
cur = head
# 第2遍遍历，为copy节点进行next和random指针的链接
while cur!=None:
# copy节点的next指向原节点的next的copy
dic[cur].next = dic[cur.next] if cur.next else None
# copy节点的random指向原节点的next的random
dic[cur].random = dic[cur.random] if cur.random else None
# 移动指针，继续下一个节点
cur = cur.next# 返回头节点的copy，即复制链表的头节点
return dic[head]推荐阅读
- Android|Android 知识点 030 —— Handler,Thread,HandlerThread
- 每日leetcode——92. 反转链表 II
- [Golang]力扣Leetcode—剑指Offer—数组—04.二维数组中的查找
- Android系统编程入门系列之硬件交互——无线通信WLAN
- 国内互联网大厂面试问题和答案|2022秋招—阿里巴巴面试高频问题和答案
- JAVA学习日记|JAVA从零开始学习知识整理——HTML——day01—【HTML】
- 开源项目分享|Github项目分享——以程序员的视角看中国
- 从零开始学WEB前端|从零开始学WEB前端——网页的行为——JavaScript基础（1）
- Leetcode 704 二分查找
- VT|VT 入门篇——最小 VT 实现（上）