【LeetCode-中等】剑指 Offer 35. 复杂链表的复制(详解)
目录
题目
方法1:错误的方法(初尝试)
方法2:复制、拆开
方法3:哈希表
总结
题目
请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。


题目地址:剑指 Offer 35. 复杂链表的复制 - 力扣(LeetCode)
或同题:138. 复制带随机指针的链表 - 力扣(LeetCode)
方法1:错误的方法(初尝试)
思路
1.先通过递归 创建新链表,每个节点的val 和 next 与旧的链表对应关系相同
2.再通过 原链表中每个节点的random的val 来找到新链表中每个节点的random的指向
这种方法是错误的方法(可以直接去看后面的方法),只是作者刚开始的尝试,错误的原因在于:每个节点的val不是唯一的,这样的话,你第2步用val来复制每个节点的random是不可以的,有些示例会过不去。
例如
输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
那么第1步的结果是:newNode = [[7,null],[13,null],[11,null],[10,null],[1,null]]
然后 第2步就是对每个节点的 random进行指向。
代码
class Solution {public Node copyRandomList(Node head) {//复制节点的val、nextNode newNode = copy(head);Node p1 = head;Node p2 = newNode;//复制节点的 randomwhile (p1 != null) {if (p1.random != null) {int val = p1.random.val;p2.random = findNode(val,newNode);}p1 = p1.next;p2 = p2.next;}return newNode;}/*** 复制 Node 的 val 和 next*/Node copy(Node oldNode) {if (oldNode == null) return null;Node newNode = new Node(oldNode.val);newNode.next = copy(oldNode.next);return newNode;}/*** 找到某个节点:他属于head,并且val 是 val*/Node findNode(int val,Node head){if (head == null)return null;Node p = head;while (p!=null){if (p.val == val)return p;p = p.next;}return null;}
}
方法2:复制、拆开
思路来自
作者:王尼玛链接:https://leetcode.cn/problems/copy-list-with-random-pointer/solutions/295083/liang-chong-shi-xian-tu-jie-138-fu-zhi-dai-sui-ji-/来源:力扣(LeetCode)著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

第一步,根据遍历到的原节点创建对应的新节点,每个新创建的节点是在原节点后面,比如下图中原节点1不再指向原原节点2,而是指向新节点1
第二步是最关键的一步,用来设置新链表的随机指针
上图中,我们可以观察到这么一个规律
原节点1的随机指针指向原节点3,新节点1的随机指针指向的是原节点3的next
原节点3的随机指针指向原节点2,新节点3的随机指针指向的是原节点2的next
也就是,原节点i的随机指针(如果有的话),指向的是原节点j
那么新节点i的随机指针,指向的是原节点j的next
第三步就简单了,只要将两个链表分离开,再返回新链表就可以了

代码
class Solution {public Node copyRandomList(Node head) {if(head==null) {return null;}Node p = head;//第一步,在每个原节点后面创建一个新节点//1->1'->2->2'->3->3'while(p!=null) {Node newNode = new Node(p.val);newNode.next = p.next;p.next = newNode;p = newNode.next;}p = head;//第二步,设置新节点的随机节点while(p!=null) {if(p.random!=null) {p.next.random = p.random.next;}p = p.next.next;}//第三步,将两个链表分离(注意这里是分离,不能修改原来的链表)Node res = new Node(-1);Node oldNode = head;Node newNode = res;while (oldNode!=null){newNode.next = oldNode.next;newNode = newNode.next;oldNode.next = newNode.next;oldNode = oldNode.next;}return res.next;}
}
方法3:哈希表
思路
思路来自
作者:王尼玛链接:https://leetcode.cn/problems/copy-list-with-random-pointer/solutions/295083/liang-chong-shi-xian-tu-jie-138-fu-zhi-dai-sui-ji-/来源:力扣(LeetCode)著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
我们用哈希表来解决这个问题
首先创建一个哈希表,再遍历原链表,遍历的同时再不断创建新节点
我们将原节点作为key,新节点作为value放入哈希表中
第二步我们再遍历原链表,这次我们要将新链表的next和random指针给设置上

从上图中我们可以发现,原节点和新节点是一一对应的关系,所以
- map.get(原节点),得到的就是对应的新节点
- map.get(原节点.next),得到的就是对应的新节点.next
- map.get(原节点.random),得到的就是对应的新节点.random
所以,我们只需要再次遍历原链表,然后设置:
新节点.next -> map.get(原节点.next)
新节点.random -> map.get(原节点.random)
这样新链表的next和random都被串联起来了
最后,我们然后map.get(head),也就是对应的新链表的头节点,就可以解决此问题了。
代码
class Solution {public Node copyRandomList(Node head) {if(head==null) {return null;}//创建一个哈希表,key是原节点,value是新节点Map<Node,Node> map = new HashMap<Node,Node>();Node p = head;//将原节点和新节点放入哈希表中while(p!=null) {Node newNode = new Node(p.val);map.put(p,newNode);p = p.next;}p = head;//遍历原链表,设置新节点的next和randomwhile(p!=null) {Node newNode = map.get(p);//p是原节点,map.get(p)是对应的新节点,p.next是原节点的下一个//map.get(p.next)是原节点下一个对应的新节点if(p.next!=null) {newNode.next = map.get(p.next);}//p.random是原节点随机指向//map.get(p.random)是原节点随机指向 对应的新节点 if(p.random!=null) {newNode.random = map.get(p.random);}p = p.next;}//返回头结点,即原节点对应的value(新节点)return map.get(head);}
}
总结
最好的方法我觉得还是方法3,这个方法不仅思路简单,代码也简单。方法2虽然思路简单,但是写代码不好写,所以要多去想哈希表,原来哈希表的key 和 value 可以分别存放两个链表,所以以后看到复杂链表的复制,要去想用哈希表来复制。
相关文章:
【LeetCode-中等】剑指 Offer 35. 复杂链表的复制(详解)
目录 题目 方法1:错误的方法(初尝试) 方法2:复制、拆开 方法3:哈希表 总结 题目 请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节…...
QT图形视图系统 - 使用一个项目来学习QT的图形视图框架 -第一篇
文章目录 QT图形视图系统介绍开始搭建MainWindow框架设置scene的属性缩放功能的添加加上标尺 QT图形视图系统 介绍 详细的介绍可以看QT的官方助手,那里面介绍的详细且明白,需要一定的英语基础,我这里直接使用一个开源项目来介绍QGraphicsVi…...
Cat.1如何成为物联网业务加速器?
随着Cat.1芯片及模组在功耗和成本上的不断优化,在窄带物联网领域,越来越多的终端客户把Cat.1当做与NB-IoT相比较的第二选择。越来越多的表计、烟感、市政等行业终端将Cat.1模组应用于非集中化部署的上报类终端业务中,Cat.1这只“网红猫”仍保…...
Qt应用开发(基础篇)——布局管理 Layout Management
目录 一、前言 二:相关类 三、水平、垂直、网格和表单布局 四、尺寸策略 一、前言 在实际项目开发中,经常需要使用到布局,让控件自动排列,不仅节省控件还易于管控。Qt布局系统提供了一种简单而强大的方式来自动布局小部件中的…...
Python web实战之 Django 的 ORM 框架详解
本文关键词:Python、Django、ORM。 概要 在 Python Web 开发中,ORM(Object-Relational Mapping,对象关系映射)是一个非常重要的概念。ORM 框架可以让我们不用编写 SQL 语句,就能够使用对象的方式来操作数据…...
pycharm制作柱状图
Bar - Bar_rotate_xaxis_label 解决标签名字过长的问题 from pyecharts import options as opts from pyecharts.charts import Barc (Bar().add_xaxis(["高等数学1,2","C语言程序设计","python程序设计","大数据导论",…...
静态资源导入探究
静态资源可以在哪里找呢?我们看看源码 从这个类进去 里面有个静态类 WebMvcAutoConfigurationAdapter 有个配置类,将这个类的对象创建并导入IOC容器里 这个静态类下有个方法 addResourceHandlers(ResourceHandlerRegistry registry)静态资源处理器 若自…...
安全狗V3.512048版本绕过
安全狗安装 安全狗详细安装、遇见无此服务器解决、在windows中命令提示符中进入查看指定文件夹手动启动Apache_安全狗只支持 glibc_2.14 但是服务器是2.17_黑色地带(崛起)的博客-CSDN博客 安全狗 safedogwzApacheV3.5.exe 右键电脑右下角安全狗图标-->选择插件-->安装…...
prometheus监控k8s kube-proxy target down
prometheus kube-proxy target down 解决 修改配置 kubectl edit cm/kube-proxy -n kube-systemmetricsBindAddress: "0.0.0.0:10249"删除 kube-proxy pod 使之重启应用配置 kubectl delete pod --force `kubectl get pod -n kube-system |grep kube-proxy|awk {pr…...
SPSS数据分析--假设检验的两种原假设取舍决定方式
假设检验的两种原假设取舍决定方式 在t检验,相关分析,回归分析,方差分析,卡方检验等等分析方法中,都需要用到假设检验。假设检验的步骤一般如下: 提出假设:H0 vs H1 ;假设原假设H0 成立的情况…...
Python实现猫狗分类
不废话了,直接上代码: def load_imagepath_from_csv(csv_name):image_path []with open(csv_name,r) as file:csv_reader csv.reader(file)next(csv_reader)for row in csv_reader:image_path.append(row[0])return image_pathimport csv csv_name &…...
pjsip、pjsua2+bcg729 windows下编译java版本
文章目录 简要说明流程步骤 简要说明 基本参考的这里 https://docs.pjsip.org/en/latest/get-started/windows/build_instructions.html#building-the-projects 我这里主要是为了生成pjsua2.dll 用于在java下调用。 其中 libbcg729.dll 是通过vcpkg来进行安装。 pjsip使用vs2…...
尝试多数据表 sqlite
C 唯一值得骄傲的地方就是 通过指针来回寻址 😂 提高使用的灵活性 小脚本buff 加成...
Keil出现Flash Timeout.Reset the Target and try it again.我有一种解决方法
2.解决方法 网上查找了找原因,是因为之前代码设置了读保护功能。 读保护即大家通常说的“加密”,是作用于整个Flash存储区域。一旦设置了Flash的读保护,内置的Flash存储区只能通过程序的正常执行才能读出,而不能通过下述任何一种…...
纯粹即刻,畅享音乐搜索的轻松体验
纯粹即刻,畅享音乐搜索的轻松体验 在当今快节奏的生活中,我们常常渴望一种简单而便捷的方式来探索和享受音乐。现在,你可以纯粹即刻地畅享音乐搜索的轻松体验。无论你是寻找热门歌曲还是探索不同风格的音乐,这款应用将为你带来随…...
动态规划之树形DP
动态规划之树形DP 树形DP何为树形DP 树形DP例题HDU-1520 Anniversary partyHDU-2196 Computer834. 树中距离之和 树形DP 何为树形DP 树形DP是指在“树”这种数据结构上进行的动态规划:给出一颗树,要求以最少的代价(或取得最大收益ÿ…...
嵌入式_GD32使用宏开关进行Debug串口打印调试
嵌入式_GD32使用宏开关进行Debug串口打印调试 串口Debug是一种将数据通过串口发送的方法。通过使用printf函数,我们可以将需要发送的数据格式化为字符串,并通过串口发送出去。在C语言中,通常使用串口发送数据的函数为printf函数,…...
使用 GitHub Copilot 进行 Prompt Engineering 的初学者指南(译)
文章目录 什么是 GitHub Copilot ?GitHub Copilot 可以自己编码吗?GitHub Copilot 的底层是如何工作的?什么是 prompt engineering?这是 prompt engineering 的另一个例子 使用 GitHub Copilot 进行 prompt engineering 的最佳实践提供高级上下文&…...
c++开发模式,享元模式
享元模式,个人理解,就是应用共享技术来减少类的对象创建,节省计算机资源消耗,而且能够减少维护成本 #include <iostream> #include <string> #include <vector>using namespace std;class Flyweight { public:…...
LLM大模型——langchain相关知识总结
目录 一、简介LangChain的主要价值支柱简单安装 二、 LangChain的主要模块1.Model I/Oprompt模版定义调用语言模型 2. 数据连接3. chains4. Agents5. MemoryCallbacks 三、其他记录多进程调用 主要参考以下开源文档 文档地址:https://python.langchain.com/en/lates…...
19c补丁后oracle属主变化,导致不能识别磁盘组
补丁后服务器重启,数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后,存在与用户组权限相关的问题。具体表现为,Oracle 实例的运行用户(oracle)和集…...
K8S认证|CKS题库+答案| 11. AppArmor
目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作: 1)、切换集群 2)、切换节点 3)、切换到 apparmor 的目录 4)、执行 apparmor 策略模块 5)、修改 pod 文件 6)、…...
SciencePlots——绘制论文中的图片
文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了:一行…...
什么是库存周转?如何用进销存系统提高库存周转率?
你可能听说过这样一句话: “利润不是赚出来的,是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业,很多企业看着销售不错,账上却没钱、利润也不见了,一翻库存才发现: 一堆卖不动的旧货…...
UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)
UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中,UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化…...
如何理解 IP 数据报中的 TTL?
目录 前言理解 前言 面试灵魂一问:说说对 IP 数据报中 TTL 的理解?我们都知道,IP 数据报由首部和数据两部分组成,首部又分为两部分:固定部分和可变部分,共占 20 字节,而即将讨论的 TTL 就位于首…...
Pinocchio 库详解及其在足式机器人上的应用
Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库,专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性,并提供了一个通用的框架&…...
九天毕昇深度学习平台 | 如何安装库?
pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子: 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...
云原生安全实战:API网关Kong的鉴权与限流详解
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关(API Gateway) API网关是微服务架构中的核心组件,负责统一管理所有API的流量入口。它像一座…...
LOOI机器人的技术实现解析:从手势识别到边缘检测
LOOI机器人作为一款创新的AI硬件产品,通过将智能手机转变为具有情感交互能力的桌面机器人,展示了前沿AI技术与传统硬件设计的完美结合。作为AI与玩具领域的专家,我将全面解析LOOI的技术实现架构,特别是其手势识别、物体识别和环境…...
