LeetCode 第 138 题:复制带随机指针的链表(Python 代码)

简介: 给定一个长度为 n 的链表,每个节点比普通的节点多了一个额外的随机指针 ramdom,该指针可以指向链表中的任何节点或空节点。构造这个链表的深拷贝。所谓的深拷贝,就是完全生成一个新的对象,内存地址都是不同的,这样改变拷贝之前变量,就不会影响到拷贝的变量。

题目 138. 复制带随机指针的链表 的描述如下,给定一个长度为 n 的链表,每个节点比普通的节点多了一个额外的随机指针 ramdom,该指针可以指向链表中的任何节点或空节点。构造这个链表的深拷贝。所谓的深拷贝,就是完全生成一个新的对象,内存地址都是不同的,这样改变拷贝之前变量,就不会影响到拷贝的变量。

哈希映射 1

首先贴一个比较巧妙的解法,来自用户 skyliuhc,在官方题解下面的评论可以看到,他写的是 Java 的版本,这里我写成 Python 的版本:

主要的思路就是,先用一个循环把新旧链表对应的两个结点捆绑在一个二元组里,然后再用一个循环完成对新链表每个结点的 nextrandom 的赋值

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head: return None
        cur = head
        hashmap = {}  # 哈希表
        # 第一个循环,建立映射
        while cur:
            hashmap[cur] = Node(cur.val)  # 新旧链表对应结点映射
            cur = cur.next  # 当前结点往后移动
        # 第二个循环,next 和 random 赋值
        cur = head
        while cur:
            # 因为 Python 的字典中不能用 None 作为键值,所以要做一个特殊判断
            hashmap[cur].next = hashmap[cur.next] if cur.next else None
            hashmap[cur].random = hashmap[cur.random] if cur.random else None
            cur = cur.next
        return hashmap[head]
AI 代码解读

哈希映射 2

这个是我自己当时做题的时候想的方法,与前面一个的想法类似,也是打算用哈希表来记录新旧链表的结点,但是想法更为复杂了,具体的思路为:

  • 1、先把最普通的链表构建起来,同时记录两个 Hashmap

    • 1.1、Node2Pos:旧链表的每个 Node 的位置
    • 1.2、Pos2Node:新链表每个位置对应的 Node
  • 2、同步遍历新旧两个链表,得到当前位置的旧节点的 random node 对应的位置 pos
  • 3、通过位置 pos 得到新链表的 Node,就知道当前结点的 random 要指向哪里;
class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head: return None
        Node2Pos = {}  # 旧链表的每个 `Node` 的位置
        Pos2Node = {}  # 新链表每个位置对应的 `Node`
        # 构建新链表
        newPreHead = Node(0)  # 前置结点
        new_ptr = newPreHead  # 新链表的头结点
        old_ptr = head  # 旧链表的头结点 
        idx = 0 # 当前的位置
        while old_ptr: 
            Node2Pos[old_ptr] = idx  # 记录旧结点位置
            new_ptr.next = Node(old_ptr.val)
            new_ptr = new_ptr.next
            Pos2Node[idx] = new_ptr  # 记录当前位置的新结点
            idx += 1  # 位置也要同步往后
            old_ptr = old_ptr.next
        Pos2Node[idx] = None  # 最后一个位置是空指针 None
        
        # 处理 random node
        new_ptr = newPreHead.next
        old_ptr = head
        while old_ptr:
            random_node = old_ptr.random  # 获得旧结点的随机结点
            # 获得旧结点随机结点的位置,如果为随机结点为空代表是最后一个位置,即 idx
            pos = Node2Pos[random_node] if random_node else idx
            node = Pos2Node[pos]  # 获得对应 pos 的结点
            new_ptr.random = node
            new_ptr = new_ptr.next
            old_ptr = old_ptr.next
        
        return newPreHead.next  # 返回结果
AI 代码解读

回溯 + 哈希表

官方题解:利用回溯法,让每个节点的拷贝操作相互独立,对于当前结点,首先进行拷贝,然后进行「当前节点的后继节点」和「当前节点的随机指针指向的节点」拷贝,拷贝完成后将创建的新节点的指针返回,即可完成当前节点的两指针的赋值。

具体的做法是:

  • 先创建一个哈希表 cachedNode,从头结点开始遍历;
  • 如果结点为空,返回 None
  • 创建一个新的结点,其值与当前遍历的结点值 val 一样;
  • 然后遍历地去对 nextrandom 赋值;
class Solution:
    def __init__(self,):
        self.cachedNode = {}
    
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head: return None
        if head not in self.cachedNode.keys():
            headNew = Node(head.val)  # 拷贝新节点
            self.cachedNode[head] = headNew  # 记录到哈希表中
            headNew.next = self.copyRandomList(head.next)
            headNew.random = self.copyRandomList(head.random)
        return self.cachedNode[head]
AI 代码解读

迭代 + 节点拆分

  • 对于链表 A => B => C,可以将其变成 A => A' => B => B' => C => C',其中 A'A 的拷贝结点
class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head: return None
        # 将 A => B 变成 A => A' => B => B'
        node = head
        while node:
            nodeNew = Node(node.val)
            nodeNew.next = node.next
            node.next = nodeNew
            node = node.next.next
        
        # 处理 random
        node = head
        while node:
            nodeNew = node.next
            nodeNew.random = node.random.next if node.random else None
            node = node.next.next
            
        # 将 A => A' => B => B' 变成 A => B
        headNew = head.next
        node = head
        while node:
            nodeNew = node.next
            node.next = node.next.next
            nodeNew.next = nodeNew.next.next if nodeNew.next else None
            node = node.next
        
        return headNew
AI 代码解读
目录
打赏
0
0
0
0
3
分享
相关文章
|
10天前
|
时间序列异常检测:MSET-SPRT组合方法的原理和Python代码实现
MSET-SPRT是一种结合多元状态估计技术(MSET)与序贯概率比检验(SPRT)的混合框架,专为高维度、强关联数据流的异常检测设计。MSET通过历史数据建模估计系统预期状态,SPRT基于统计推断判定偏差显著性,二者协同实现精准高效的异常识别。本文以Python为例,展示其在模拟数据中的应用,证明其在工业监控、设备健康管理及网络安全等领域的可靠性与有效性。
498 8
时间序列异常检测:MSET-SPRT组合方法的原理和Python代码实现
【Azure Developer】分享两段Python代码处理表格(CSV格式)数据 : 根据每列的内容生成SQL语句
本文介绍了使用Python Pandas处理数据收集任务中格式不统一的问题。针对两种情况:服务名对应多人拥有状态(1/0表示),以及服务名与人名重复列的情况,分别采用双层for循环和字典数据结构实现数据转换,最终生成Name对应的Services列表(逗号分隔)。此方法高效解决大量数据的人工处理难题,减少错误并提升效率。文中附带代码示例及执行结果截图,便于理解和实践。
实战指南:通过1688开放平台API获取商品详情数据(附Python代码及避坑指南)
1688作为国内最大的B2B供应链平台,其API为企业提供合法合规的JSON数据源,直接获取批发价、SKU库存等核心数据。相比爬虫方案,官方API避免了反爬严格、数据缺失和法律风险等问题。企业接入1688商品API需完成资质认证、创建应用、签名机制解析及调用接口四步。应用场景包括智能采购系统、供应商评估模型和跨境选品分析。提供高频问题解决方案及安全合规实践,确保数据安全与合法使用。立即访问1688开放平台,解锁B2B数据宝藏!
【Azure Developer】编写Python SDK代码实现从China Azure中VM Disk中创建磁盘快照Snapshot
本文介绍如何使用Python SDK为中国区微软云(China Azure)中的虚拟机磁盘创建快照。通过Azure Python SDK的Snapshot Class,指定`location`和`creation_data`参数,使用`Copy`选项从现有磁盘创建快照。代码示例展示了如何配置Default Azure Credential,并设置特定于中国区Azure的`base_url`和`credential_scopes`。参考资料包括官方文档和相关API说明。
|
3月前
|
Python高性能编程:五种核心优化技术的原理与Python代码
Python在高性能应用场景中常因执行速度不及C、C++等编译型语言而受质疑,但通过合理利用标准库的优化特性,如`__slots__`机制、列表推导式、`@lru_cache`装饰器和生成器等,可以显著提升代码效率。本文详细介绍了这些实用的性能优化技术,帮助开发者在不牺牲代码质量的前提下提高程序性能。实验数据表明,这些优化方法能在内存使用和计算效率方面带来显著改进,适用于大规模数据处理、递归计算等场景。
96 5
Python高性能编程:五种核心优化技术的原理与Python代码
|
4月前
|
课程设计项目之基于Python实现围棋游戏代码
游戏进去默认为九路玩法,当然也可以选择十三路或是十九路玩法 使用pycharam打开项目,pip安装模块并引用,然后运行即可, 代码每行都有详细的注释,可以做课程设计或者毕业设计项目参考
95 33
【Azure Developer】Python代码调用Graph API将外部用户添加到组,结果无效,也无错误信息
根据Graph API文档,在单个请求中将多个成员添加到组时,Python代码示例中的`members@odata.bind`被错误写为`members@odata_bind`,导致用户未成功添加。
65 10
以下是一些常用的图表类型及其Python代码示例,使用Matplotlib和Seaborn库。
通过这些思维导图和分析说明表,您可以更直观地理解和选择适合的数据可视化图表类型,帮助更有效地展示和分析数据。
147 8
深入理解Python装饰器:提升代码重用与可读性
本文旨在为中高级Python开发者提供一份关于装饰器的深度解析。通过探讨装饰器的基本原理、类型以及在实际项目中的应用案例,帮助读者更好地理解并运用这一强大的语言特性。不同于常规摘要,本文将以一个实际的软件开发场景引入,逐步揭示装饰器如何优化代码结构,提高开发效率和代码质量。
93 6
探索Python中的装饰器:简化代码,增强功能
在Python的世界里,装饰器就像是给函数穿上了一件神奇的外套,让它们拥有了超能力。本文将通过浅显易懂的语言和生动的比喻,带你了解装饰器的基本概念、使用方法以及它们如何让你的代码变得更加简洁高效。让我们一起揭开装饰器的神秘面纱,看看它是如何在不改变函数核心逻辑的情况下,为函数增添新功能的吧!
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等