字节跳动笔试题——复杂链表的复杂——剑指 Offer 35. 复杂链表的复制——python && C++源代码

简介: 字节跳动笔试题——复杂链表的复杂——剑指 Offer 35. 复杂链表的复制——python && C++源代码

剑指 Offer 35. 复杂链表的复制


难度中等529收藏分享切换为英文接收动态反馈


请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。


示例 1:


image.png


输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]

输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2:


image.png


输入:head = [[1,1],[2,1]]

输出:[[1,1],[2,1]]

示例 3:


image.png


输入:head = [[3,null],[3,0],[3,null]]

输出:[[3,null],[3,0],[3,null]]

示例 4:


输入:head = []

输出:[]

解释:给定的链表为空(空指针),因此返回 null。

提示:


-10000 <= Node.val <= 10000

Node.random 为空(null)或指向链表中的节点。

节点数目不超过 1000 。

解题思路:

哈希+字典序


相比较普通的链表复制,增加了一个随机的,其实也很简单,使用字典将随机的那个也放到字典即可,然后输出我们想要的


Python代码:

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head: return
        ym = head
        ans = {}
        while ym:
            ans[ym] = Node(ym.val)
            ym = ym.next
        ym = head
        while ym:
            ans[ym].next = ans.get(ym.next)
            ans[ym].random = ans.get(ym.random)
            ym = ym.next
        return ans[head]

C++代码:

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head: return
        ym = head
        ans = {}
        while ym:
            ans[ym] = Node(ym.val)
            ym = ym.next
        ym = head
        while ym:
            ans[ym].next = ans.get(ym.next)
            ans[ym].random = ans.get(ym.random)
            ym = ym.next
        return ans[head]
相关文章
|
6天前
|
jenkins Shell 测试技术
|
6天前
|
安全 jenkins Java
Java、Python、C++支持jenkins和SonarQube(一)
Jenkins 是一个开源的 持续集成(CI)和持续交付(CD) 工具,用于自动化构建、测试和部署软件项目。它基于 Java 开发,支持跨平台运行,并拥有丰富的插件生态系统,可以灵活地扩展功能
44 5
|
6天前
|
jenkins Java Shell
Java、Python、C++支持jenkins和SonarQube(全集)
Jenkins 是一个开源的持续集成(CI)和持续交付(CD)工具,用于自动化构建、测试和部署软件项目。它基于 Java 开发,支持跨平台运行,并拥有丰富的插件生态系统,可以灵活地扩展功能
77 1
|
6天前
|
jenkins Java 持续交付
|
6天前
|
jenkins Java 测试技术
|
5月前
|
存储 Python
Python 中链表的个人理解
简介:本文介绍了Python中链表的基本组成及其操作实现。链表由`head`(头节点)、中间节点和`tail`(尾节点)三部分构成,每个节点通过`Node`类定义,包含`value`(值域)和`next`(指针域)。示例代码展示了链表的增删查功能,包括`add`(头部插入)、`append`(尾部插入)、`remove`(删除节点)、`search`(查找节点)及遍历方法。运行结果验证了链表操作的正确性。
|
7月前
|
存储 Python
Python 实现单向链表,和单向链表的反转
链表是一种数据结构,每个节点存储相邻节点的位置信息。单链表中的节点仅存储下一节点的位置。通过Python实现单链表,定义`ListNode`类并关联节点可创建链表。例如,创建A-&gt;B-&gt;C的链表后,可通过反转函数`reverse`将链表反转为CBA。代码展示了如何实现和操作单链表。
140 6
Python 实现单向链表,和单向链表的反转
|
7月前
|
算法 Serverless 数据处理
从集思录可转债数据探秘:Python与C++实现的移动平均算法应用
本文探讨了如何利用移动平均算法分析集思录提供的可转债数据,帮助投资者把握价格趋势。通过Python和C++两种编程语言实现简单移动平均(SMA),展示了数据处理的具体方法。Python代码借助`pandas`库轻松计算5日SMA,而C++代码则通过高效的数据处理展示了SMA的计算过程。集思录平台提供了详尽且及时的可转债数据,助力投资者结合算法与社区讨论,做出更明智的投资决策。掌握这些工具和技术,有助于在复杂多变的金融市场中挖掘更多价值。
240 12
|
7月前
|
存储 算法 搜索推荐
Python 实现反转、合并链表有啥用?
大家好,我是V哥。本文介绍Python实现反转链表和合并链表的应用场景及代码实现。反转链表适用于时间序列数据展示、回文链表判断等;合并链表则用于大规模数据排序、数据库查询结果集合并等。通过迭代和递归方法实现反转链表,以及合并两个或多个有序链表的算法,帮助开发者解决实际问题。关注V哥,了解更多实用编程技巧。 先赞再看后评论,腰缠万贯财进门。
120 0

推荐镜像

更多