LeetCode如何实现复杂链表的复制
这篇文章主要为大家展示了“LeetCode如何实现复杂链表的复制”，内容简而易懂，条理清晰，希望能够帮助大家解决疑惑，下面让小编带领大家一起研究并学习一下“LeetCode如何实现复杂链表的复制”这篇文章吧。
涧西网站建设公司创新互联公司,涧西网站设计制作，有大型网站制作公司丰富经验。已为涧西千余家提供企业网站建设服务。企业网站搭建\外贸网站建设要多少钱，请找那个售后服务好的涧西做网站的公司定做！
题目描述
请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
-10000 <= Node.val <= 10000 Node.random 为空（null）或指向链表中的节点。 节点数目不超过 1000 。
题目样例
示例
输入
head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出
[[7,null],[13,0],[11,4],[10,2],[1,0]]
题目思考
如何处理 random 指针?
解决方案
思路
如果只有 next 指针的话很简单, 我们只需要对每个节点新建一个相同值的节点, 并保持指向关系, 逐个遍历过去即可 现在多了个 random 指针, 想要定位新的指向的节点, 一个比较自然的想法就是额外维护一个老节点到新节点的映射关系, 可以用字典来实现 第一遍遍历, 就只关注 next 部分, 并建立好映射关系 第二遍遍历, 考虑 random 部分, 找到对应的新链表的节点, 然后当前节点的 random 指针指向它即可
复杂度
时间复杂度 O(N)每个节点只需要遍历两次 空间复杂度 O(N)额外需要一个字典
代码
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
if not head:
return None
maps = {}
# 第一遍遍历, 建立新的链表, 以及老节点到新节点的映射关系
copyHead = Node(head.val)
origin, copy = head, copyHead
maps[origin] = copy
while origin.next:
# 新建下一个节点, 并建立next关系
copy.next = Node(origin.next.val)
origin = origin.next
copy = copy.next
maps[origin] = copy
# 第二遍遍历, 处理random指针部分
origin, copy = head, copyHead
while origin:
if origin.random:
# 如果老节点random指针指向非空的话, 就将当前新节点也指向随机节点对应的新节点
copy.random = maps[origin.random]
origin = origin.next
copy = copy.next
return copyHead以上是“LeetCode如何实现复杂链表的复制”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注创新互联行业资讯频道！
分享名称：LeetCode如何实现复杂链表的复制
地址分享：http://cdiso.cn/article/gpgjss.html
