当前位置: 首页 > 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;并且可以选择每页显示的条数试试更新总页数及显示当…...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

conda相比python好处

Conda 作为 Python 的环境和包管理工具&#xff0c;相比原生 Python 生态&#xff08;如 pip 虚拟环境&#xff09;有许多独特优势&#xff0c;尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处&#xff1a; 一、一站式环境管理&#xff1a…...

Appium+python自动化(十六)- ADB命令

简介 Android 调试桥(adb)是多种用途的工具&#xff0c;该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具&#xff0c;其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利&#xff0c;如安装和调试…...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

页面渲染流程与性能优化

页面渲染流程与性能优化详解&#xff08;完整版&#xff09; 一、现代浏览器渲染流程&#xff08;详细说明&#xff09; 1. 构建DOM树 浏览器接收到HTML文档后&#xff0c;会逐步解析并构建DOM&#xff08;Document Object Model&#xff09;树。具体过程如下&#xff1a; (…...

SpringTask-03.入门案例

一.入门案例 启动类&#xff1a; package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...