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

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

【大模型RAG】Docker 一键部署 Milvus 完整攻略

本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装&#xff1b;只需暴露 19530&#xff08;gRPC&#xff09;与 9091&#xff08;HTTP/WebUI&#xff09;两个端口&#xff0c;即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

招商蛇口 | 执笔CID,启幕低密生活新境

作为中国城市生长的力量&#xff0c;招商蛇口以“美好生活承载者”为使命&#xff0c;深耕全球111座城市&#xff0c;以央企担当匠造时代理想人居。从深圳湾的开拓基因到西安高新CID的战略落子&#xff0c;招商蛇口始终与城市发展同频共振&#xff0c;以建筑诠释对土地与生活的…...

pycharm 设置环境出错

pycharm 设置环境出错 pycharm 新建项目&#xff0c;设置虚拟环境&#xff0c;出错 pycharm 出错 Cannot open Local Failed to start [powershell.exe, -NoExit, -ExecutionPolicy, Bypass, -File, C:\Program Files\JetBrains\PyCharm 2024.1.3\plugins\terminal\shell-int…...

区块链技术概述

区块链技术是一种去中心化、分布式账本技术&#xff0c;通过密码学、共识机制和智能合约等核心组件&#xff0c;实现数据不可篡改、透明可追溯的系统。 一、核心技术 1. 去中心化 特点&#xff1a;数据存储在网络中的多个节点&#xff08;计算机&#xff09;&#xff0c;而非…...

阿里云Ubuntu 22.04 64位搭建Flask流程(亲测)

cd /home 进入home盘 安装虚拟环境&#xff1a; 1、安装virtualenv pip install virtualenv 2.创建新的虚拟环境&#xff1a; virtualenv myenv 3、激活虚拟环境&#xff08;激活环境可以在当前环境下安装包&#xff09; source myenv/bin/activate 此时&#xff0c;终端…...