当前位置: 首页 > news >正文

【数据结构】_链表经典算法OJ:复杂链表的复制

目录

1. 题目链接及描述

2. 解题思路

3. 程序


1. 题目链接及描述

题目链接:138. 随机链表的复制 - 力扣(LeetCode)

题目描述:

给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点(拷贝结点的核心解决点)

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如,如果原链表中有 X 和 Y 两个节点,其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ,同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。

每个节点用一个 [val, random_index] 表示:

val:一个表示 Node.val 的整数。
random_index:随机指针指向的节点索引(范围从 0 到 n-1);如果不指向任何节点,则为null。
你的代码 只 接受原链表的头节点 head 作为传入参数。

2. 解题思路

依次拷贝原链表的每一个结点,将拷贝结点插入在源结点的后面,则random指向的结点与拷贝后的结点对应的相对距离是相同的。

具体实现分为三大步:
第一步:遍历原链表,逐个拷贝结点,并将拷贝结点插入原结点的后面(此步需处理每个结点的next域);

第二步:逐个处理拷贝结点的random域:

 以题示例为例,依次插入copy结点后,以第二个结点为例,观察cur->random与copy->random的关系:

第三步:从原链表中逐个拆解拷贝结点,将其逐个尾插构成一个新链表,记新链表的第一个结点为copyHead,返回copyHead即可;

注:对于原链表是否进行恢复可自行选择。

3. 程序

/*** Definition for a Node.* struct Node {*     int val;*     struct Node *next;*     struct Node *random;* };*/
typedef struct Node Node;
struct Node* copyRandomList(struct Node* head) {Node* cur = head;// Node* curNext=cur->next;// 依次创建原链表每个结点的拷贝结点// 将每个拷贝结点链到原结点的后面:修改next域while (cur) {Node* copy = (Node*)malloc(sizeof(Node));copy->val = cur->val;// 将copy链入原链表copy->next = cur->next;cur->next = copy;// 更新curcur = copy->next;}// 修改random域cur = head;while (cur) {Node* copy = cur->next;if (cur->random == NULL) {copy->random = NULL;} else {copy->random = cur->random->next;}// 更新curcur = copy->next;}// 从原链表中拆解拷贝链表// 依次取copy结点尾插到新链表Node *copyHead = NULL, *copyTail = NULL;cur = head;while (cur) {Node* copy = cur->next;Node* copyNext = copy->next;// 单独处理拷贝链表为空的情况if (copyTail == NULL) {copyHead = copyTail = copy;} else {// 尾插copy并更新copyTailcopyTail->next = copy;copyTail = copyTail->next;}// 更新cur与copycur=copy->next;}return copyHead;
}

相关文章:

【数据结构】_链表经典算法OJ:复杂链表的复制

目录 1. 题目链接及描述 2. 解题思路 3. 程序 1. 题目链接及描述 题目链接:138. 随机链表的复制 - 力扣(LeetCode) 题目描述: 给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,…...

Vue 图片引用方式详解:静态资源与动态路径访问

目录 前言1. 引用 public/ 目录2. assets/ 目录3. 远程服务器4. Vue Router 动态访问5. 总结6. 扩展(图片不显示) 前言 🤟 找工作,来万码优才:👉 #小程序://万码优才/r6rqmzDaXpYkJZF 在 Vue 开发中&#x…...

chatGPT写的网页版贪吃蛇小游戏

chatGPT写的网页版贪吃蛇小游戏 前言网页版贪吃蛇小游戏 前言 之前无聊,让ChatGPT写了一段基于html语言的贪吃蛇小游戏代码 网页版贪吃蛇小游戏 将以下内容复制到记事本,重命名为xxx.html即可打开浏览器游玩 这里是一个使用HTML、CSS和JavaScript编写…...

Python量化交易助手:xtquant的安装与应用

Python量化交易助手:xtquant的安装与应用 技术背景和应用场景 在量化交易领域,Python因其强大的库支持和灵活性成为了许多开发者的首选语言。其中,xtquant 是迅投官方开发的一个Python包,专门用于与miniqmt通信,实现…...

前缀和算法

文章目录 算法总览题目1371.每个元音包含偶数次的最长子字符串 算法总览 题目 1371.每个元音包含偶数次的最长子字符串 1371.每个元音包含偶数次的最长子字符串 参考博主的讲解 思路分析:就是得使用前缀和记录情况,dp[i][j]表示s[0] 到s[i] 中&…...

Qt常用控件 输入类控件

文章目录 1.QLineEdit1.1 常用属性1.2 常用信号1.3 例子1,录入用户信息1.4 例子2,正则验证手机号1.5 例子3,验证输入的密码1.6 例子4,显示密码 2. QTextEdit2.1 常用属性2.2 常用信号2.3 例子1,获取输入框的内容2.4 例…...

《最小阻力之路》关于愿景的理解和思考

一、愿景的形成机制 1. 愿景的三层来源 来源层级形成机制案例潜在偏差风险① 本能冲动层对快感/痛苦的即时反应"想暴富"源于缺钱焦虑易被短期情绪劫持② 社会镜像层内化外界标准(家庭/社会/文化)"必须考研"因家人期待混淆他人需求…...

Ubuntu 22.04系统安装部署Kubernetes v1.29.13集群

Ubuntu 22.04系统安装部署Kubernetes v1.29.13集群 简介Kubernetes 的工作流程概述Kubernetes v1.29.13 版本Ubuntu 22.04 系统安装部署 Kubernetes v1.29.13 集群 1 环境准备1.1 集群IP规划1.2 初始化步骤(各个节点都需执行)1.2.1 主机名与IP地址解析1.…...

虚幻基础17:动画层接口

能帮到你的话,就给个赞吧 😘 文章目录 animation layer interface animation layer interface 动画层接口:动画图表的集。仅有名字。 添加到动画蓝图中,由动画蓝图实现动画图表。...

无人机PX4飞控 | PX4源码添加自定义uORB消息并保存到日志

PX4源码添加自定义uORB消息并保存到日志 0 前言 PX4的内部通信机制主要依赖于uORB(Micro Object Request Broker),这是一种跨进程的通信机制,一种轻量级的中间件,用于在PX4飞控系统的各个模块之间进行高效的数据交换…...

HTMLCSS :下雪了

这段代码创建了一个动态的雪花飘落加载动画,通过 CSS 技术实现了雪花的下落和消失效果,为页面添加了视觉吸引力和动态感。 大家复制代码时,可能会因格式转换出现错乱,导致样式失效。建议先少量复制代码进行测试,若未能…...

如何处理 Typecho Joe 主题被抄袭或盗版的问题

在开源社区中,版权保护是一个非常重要的话题。如果你发现自己的主题(如 Joe 主题)被其他主题(如子比主题)抄袭或盗版,你可以采取以下措施来维护自己的权益。 一、确认侵权行为 在采取任何行动之前&#xf…...

利用Vue和javascript分别编写一个“Hello World”的定时更新

目录 一、利用Vue编写一个“Hello World”的定时更新(1)vue编码在Html文件中(2)vue编码在js文件中 二、利用javascript编写一个“Hello World”的定时更新 一、利用Vue编写一个“Hello World”的定时更新 (1&#xff…...

volatile变量需要减少读取次数吗

问题说明 本人在前期读Netty源码时看到这样一段源码和注释: private boolean invokeHandler() {// Store in local variable to reduce volatile reads.int handlerState this.handlerState;return handlerState ADD_COMPLETE || (!ordered && handlerS…...

bootstrap.yml文件未自动加载问题解决方案

在添加bootstrap.yml文件后,程序未自动扫描到,即图标是这样的: 查了一些资料,是缺少bootstrap相关依赖,虽然已经添加了spring-cloud-context依赖,但是这个依赖并未引入bootstrap依赖,可能是版本问题,需要手动引入 <dependency><groupId>org.springframework.cloud&…...

编程AI深度实战:AI编程工具哪个好? Copilot vs Cursor vs Cody vs Supermaven vs Aider

​ 系列文章: 编程AI深度实战:私有模型deep seek r1,必会ollama-CSDN博客 编程AI深度实战:自己的AI,必会LangChain-CSDN博客 编程AI深度实战:给vim装上AI-CSDN博客 编程AI深度实战:火的编程AI,都在用语法树(AST)-CSDN博客 编程AI深度实战:让verilog不再是 AI …...

前端知识速记--CSS篇:display

前端知识速记–CSS篇&#xff1a;display 一、什么是 display 属性&#xff1f; display 属性用于指定一个元素如何被显示在网页上。它不仅影响元素的显示形式&#xff0c;还对元素的布局、结构以及与其他元素之间的关系产生重要影响。 二、常用 display 属性值 1. block …...

51单片机 01 LED

一、点亮一个LED 在STC-ISP中单片机型号选择 STC89C52RC/LE52RC&#xff1b;如果没有找到hex文件&#xff08;在objects文件夹下&#xff09;&#xff0c;在keil中options for target-output- 勾选 create hex file。 如果要修改编程 &#xff1a;重新编译-下载/编程-单片机重…...

WPF进阶 | WPF 动画特效揭秘:实现炫酷的界面交互效果

WPF进阶 | WPF 动画特效揭秘&#xff1a;实现炫酷的界面交互效果 前言一、WPF 动画基础概念1.1 什么是 WPF 动画1.2 动画的基本类型1.3 动画的核心元素 二、线性动画详解2.1 DoubleAnimation 的使用2.2 ColorAnimation 实现颜色渐变 三、关键帧动画深入3.1 DoubleAnimationUsin…...

分页按钮功能

前言 在前端开发中&#xff0c;分页功能是一个常见的需求&#xff0c;特别是当需要展示大量数据时&#xff0c;它能有效提升用户体验。该文章结合运用了HTML&#xff0c;CSS&#xff0c;JS实现网页的分页按钮功能&#xff0c;并且可以选择每页显示的条数试试更新总页数及显示当…...

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

C# 类和继承(抽象类)

抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...

HTML前端开发:JavaScript 常用事件详解

作为前端开发的核心&#xff0c;JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例&#xff1a; 1. onclick - 点击事件 当元素被单击时触发&#xff08;左键点击&#xff09; button.onclick function() {alert("按钮被点击了&#xff01;&…...

MySQL用户和授权

开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务&#xff1a; test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

【Linux】自动化构建-Make/Makefile

前言 上文我们讲到了Linux中的编译器gcc/g 【Linux】编译器gcc/g及其库的详细介绍-CSDN博客 本来我们将一个对于编译来说很重要的工具&#xff1a;make/makfile 1.背景 在一个工程中源文件不计其数&#xff0c;其按类型、功能、模块分别放在若干个目录中&#xff0c;mak…...

用鸿蒙HarmonyOS5实现中国象棋小游戏的过程

下面是一个基于鸿蒙OS (HarmonyOS) 的中国象棋小游戏的实现代码。这个实现使用Java语言和鸿蒙的Ability框架。 1. 项目结构 /src/main/java/com/example/chinesechess/├── MainAbilitySlice.java // 主界面逻辑├── ChessView.java // 游戏视图和逻辑├──…...

es6+和css3新增的特性有哪些

一&#xff1a;ECMAScript 新特性&#xff08;ES6&#xff09; ES6 (2015) - 革命性更新 1&#xff0c;记住的方法&#xff0c;从一个方法里面用到了哪些技术 1&#xff0c;let /const块级作用域声明2&#xff0c;**默认参数**&#xff1a;函数参数可以设置默认值。3&#x…...