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

OJ随机链表的复制题目分析

题目内容:

138. 随机链表的复制 - 力扣(LeetCode)

分析: 

这道题目,第一眼感觉非常乱,这是正常的,但是我们经过仔细分析示例明白后,其实也并不是那么难。现在让我们一起来分析分析吧!

1.题目要求的是链表的复制,那么我们得想我们该怎么做,才能很好地进行下去呢?

2.是直接把原链表一个一个地移动过来?这思路果断不对,它还要保持原来的链表不被复制啊.

3.经过观察,我们发现13的random指向7。各种穿插的,所以我们采用

 

//复制struct Node* cur=head;while(cur){struct Node* copy=(struct Node*)malloc(sizeof(struct Node));copy->val=cur->val;struct Node*Next=cur->next;cur->next=copy;copy->next=Next;cur=Next;}

复制部分:

先在每个数复制下来,分别放在它的原数字的下一个。即下图:

4.接着你看它原链表的那些数字。7的random指向NULL,13的random指向7.(其他的省略说)。7的next指向13。看到这种规律,我们试想是不是可以把复制的也弄成这样子,就形成了一个独立的复制链表了,对吧? 

连线部分:

 

 //连接线cur=head;while(cur){struct Node* copy=cur->next;// struct Node* Next=cur->next->next;if(cur->random==NULL){copy->random=NULL;}else{copy->random=cur->random->next;}cur=cur->next->next;}

如下图:

你看复制完了之后,是不是可以直接它复制那部分挪下来,它也是不会破坏原链表的,这是不是就符合题目要求了对吧?

5.完成了这步了之后,到了我们一个一个挪的那部分了。

如下图:

 

解释上图:

 //复制的挪下来,恢复原链表struct Node* copyhead=NULL,*copytail=NULL;cur=head; while(cur){struct Node* copy=cur->next;struct Node* Next=copy->next; //尾插if(copyhead==NULL){copyhead=copytail=copy;}else{copytail->next=copy;copytail=copytail->next;}

挪动部分:

当我们复制完了之后,开始挪新的复制链表:

1.首先定义一个cur指针指向head头。再定义一个next指针指向cur的下一个(方便它随时都能返回找到copy的位置)。

2.定义两个指针分别为copyhead和copytail指针,放在新的链表那里当作移动工具和最后返回工具

2.接着,相当于进行尾插,当 第一次时,copyhead和copytail都为空时,就把copy值直接放到这个指针

3.不为空时,就把copy值放到copytail的下一位。

恢复部分:

最后,恢复原来的链表,即去掉它copy的那些数:

1.因为我们上面都没有动过cur的位置,所以这里就直接使用cur这个指针就行了。

2.把cur的下一个给Next即:  把cur的下一个next给给cur的next的next(即cur的下下个)。

  //恢复链表cur->next=Next;cur=Next; 

总代码: 

/*** Definition for a Node.* struct Node {*     int val;*     struct Node *next;*     struct Node *random;* };*/struct Node* copyRandomList(struct Node* head) {//复制struct Node* cur=head;while(cur){struct Node* copy=(struct Node*)malloc(sizeof(struct Node));copy->val=cur->val;struct Node*Next=cur->next;cur->next=copy;copy->next=Next;cur=Next;}//连接线cur=head;while(cur){struct Node* copy=cur->next;// struct Node* Next=cur->next->next;if(cur->random==NULL){copy->random=NULL;}else{copy->random=cur->random->next;}cur=cur->next->next;}//复制的挪下来,恢复原链表struct Node* copyhead=NULL,*copytail=NULL;cur=head; while(cur){struct Node* copy=cur->next;struct Node* Next=copy->next; //尾插if(copyhead==NULL){copyhead=copytail=copy;}else{copytail->next=copy;copytail=copytail->next;}//恢复链表cur->next=Next;cur=Next; }return copyhead;
}

最后,特别要注意的是:cur的位置要每到一部分都要及时更新变成head。(因为它每一部分都在改变),不然就会像我一开始那样,发现怎么都不正确哇哇哇哇。

每次鸡汤:

好啦,到了我们的每次鸡汤部分:

虽然我每次迈出的那一步都很小,但是终究会有那么一天会到达终点的。加油吧,青年。

相关文章:

OJ随机链表的复制题目分析

题目内容: 138. 随机链表的复制 - 力扣(LeetCode) 分析: 这道题目,第一眼感觉非常乱,这是正常的,但是我们经过仔细分析示例明白后,其实也并不是那么难。现在让我们一起来分析分析…...

UE5材质节点Distance

Distance可以计算两个物体间的距离,可以用来做过渡效果 当相机和物体距离3000的时候,就会渐渐从蓝过渡到红色,除以500是为了平滑过渡...

OSPF - SPF算法简述

SPF全称最短路径树算法,相信学过数据结构朋友应该看起来很熟悉  在一个区域内的路由器都会产生描述自己网络连接信息的LSA,包括两种信息,有路由信息和拓扑信息,简单的来说拓扑信息就是我连着谁,路由信息就是链路的地址…...

7.UE5横板2D游戏,添加分类,创建攻击,死亡逻辑,黑板实现追击玩家行为

目录 1.将变量分类 2.创建攻击 3.应用伤害逻辑 4.死亡逻辑,停止AI行为 5.AI追击玩家,使用黑板实现 1.将变量分类 2.创建攻击 创建攻击输入为鼠标左键,并绑定映射。 攻击动画,在角色状态的枚举中添加一个新的枚举 攻击输入的…...

PostgreSQL对称between比较运算

本文介绍PostgreSQL对称between比较功能:between symmetric,在动态拼接SQL时利用它可以简化判断。PostgreSQL 9.4 及以上版本支持BETWEEN SYMMETRIC操作符,MySQL、Oracle、MsSQL没有对应功能。 between 比较 PostgreSQL的between结构允许你对…...

Spring AOP面向切面编程

Spring AOP面向切面编程 面向切面编程AOP作用AOP功能AOP总结 AOP核心概念AOP的实现方式Spring 对AOP支持支持Aspect声明一个切面声明一个切入点AspectJ描述符如下AspectJ类型匹配的通配符常用的匹配规则 声明增强 用AOP实现日志拦截一般的实现仅拦截需要的方法先定义一个日志注…...

Visual Studio 中增加的AI功能

前言: 人工智能的发展,在现在,编程技术的IDE里面也融合了AI的基本操做。本例,以微软的Visual Studio中的人工智能的功能介绍例子。 本例的环境: Visual Studio 17.12 1 AI 智能变量检测: 上图展示了一…...

15. 接雨水

接雨水 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 示例 1: 输入:height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出:6 解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(…...

从索尼爱立信手机打印短信的简单方法

昨天,我买了一部新手机来代替我的旧索尼爱立信Xperia,但手机上有很多珍贵的短信,是我男朋友发来的,我不想失去它们。然后我尝试打印它们,但我无法从我的索尼爱立信手机中取出它们。您有什么从索尼爱立信手机打印短信的…...

Java-list均分分割到多个子列表

在Java中,如果你有一个List并且想要将其均分到多个子列表中,可以使用以下方法。假设你有一 个List<T>,并且想要将其分成n个子列表。 import java.util.ArrayList; import java.util.List;public class ListSplitter {public static <T> List<List<T>…...

kettle合并表数据

总体执行图&#xff1a;以两个数据表作为输入&#xff0c;根据关键栏位进行合并后&#xff0c;以excel表输出。 两表数据输入 需要确定查询的表名 2. 根据关键栏位进行排序。在记录集连接之前需要进行排序操作 3. 记录连接与合并 此方式表示select EQP_ID, ID FROM T_EQP_C…...

蓝耘平台使用InstantMesh‌生成高质量的三维网格模型!3D内容创作!小白入门必看!!!

目录 引言 InstantMesh应用介绍 蓝耘平台与InstantMesh结合使用 如何部署&#xff08;超简单&#xff09; 第一步登录蓝耘平台 第二步点击应用商城 ​编辑 第三步选择InstantMesh 第四步点击部署 第五步点击快速启动应用 第六步即可体验该产品 总结 注册链接 引言…...

关于IDE的相关知识之二【插件推荐】

成长路上不孤单&#x1f60a;&#x1f60a;&#x1f60a;&#x1f60a;&#x1f60a;&#x1f60a; 【14后&#x1f60a;///计算机爱好者&#x1f60a;///持续分享所学&#x1f60a;///如有需要欢迎收藏转发///&#x1f60a;】 今日分享关于ide插件推荐的相关内容&#xff01…...

oceanbase集群访问异常问题处理

1.报错现象 2.问题排查 检查obproxy状态发现为不可用状态 重启obproxy 依次重启Obproxy集群 观察任务状态 重启完成 Obproxy状态正常 3.验证登录 登录成功...

Linux(centos)安装 MySQL 8 数据库(图文详细教程)

前言 前几天写了个window系统下安装Mysql的博客&#xff0c;收到很多小伙伴私信需要Linux下安装Mysql的教程&#xff0c;今天这边和大家分享一下&#xff0c;话不多说&#xff0c;看教程。 一、删除以前安装的MySQL服务 一般安装程序第一步都需要清除之前的安装痕迹&#xff…...

C++之map和set的模拟实现

目录 引言 红黑树迭代器实现 红黑树元素的插入 map模拟实现 set模拟实现 之前我们已经学习了map和set的基本使用&#xff0c;但是因为map和set的底层都是用红黑树进行封装实现的&#xff0c;上期我们已经学习了红黑树的模拟实现&#xff0c;所以本期我们在红黑树模拟实现…...

判断一个单链表是否是回文结构 要求O(N)时间复杂度 O(1)空间复杂度

没做出来 看了解析 但是思路想到了 就是只能调整链表顺序&#xff0c;正确答案是 把链表变成两条单链表&#xff0c;分别从两侧走向中间拿两个指针 分别指向两头 &#xff0c;往中间走 中途有不一样的就返回false, private static boolean handle(Node head){int size size…...

Kafka 快速实战及基本原理详解解析-01

一、Kafka 介绍 1. MQ 的作用 消息队列&#xff08;Message Queue&#xff0c;简称 MQ&#xff09;是一种用于跨进程通信的技术&#xff0c;核心功能是通过异步消息的方式实现系统之间的解耦。它在现代分布式系统中有着广泛的应用&#xff0c;主要作用体现在以下三个方面&…...

wujie无界微前端框架初使用

先说一下项目需求&#xff1a;将单独的四套系统的登录操作统一放在一个入口页面进行登录&#xff0c;所有系统都使用的是vue3&#xff0c;&#xff08;不要问我为啥会这样设计&#xff0c;产品说的客户要求&#xff09; 1.主系统下载wujie 我全套都是vue3&#xff0c;所以直接…...

C++ 设计模式:职责链模式(Chain of Responsibility)

链接&#xff1a;C 设计模式 链接&#xff1a;C 设计模式 - 组合模式 链接&#xff1a;C 设计模式 - 迭代器模式 职责链模式&#xff08;Chain of Responsibility Pattern&#xff09;是一种行为型设计模式&#xff0c;它允许多个对象都有机会处理请求&#xff0c;从而避免请求…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

在四层代理中还原真实客户端ngx_stream_realip_module

一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡&#xff08;如 HAProxy、AWS NLB、阿里 SLB&#xff09;发起上游连接时&#xff0c;将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后&#xff0c;ngx_stream_realip_module 从中提取原始信息…...

cf2117E

原题链接&#xff1a;https://codeforces.com/contest/2117/problem/E 题目背景&#xff1a; 给定两个数组a,b&#xff0c;可以执行多次以下操作&#xff1a;选择 i (1 < i < n - 1)&#xff0c;并设置 或&#xff0c;也可以在执行上述操作前执行一次删除任意 和 。求…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

C# 类和继承(抽象类)

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

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...