当前位置: 首页 > 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;从而避免请求…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》

在注意力分散、内容高度同质化的时代&#xff0c;情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现&#xff0c;消费者对内容的“有感”程度&#xff0c;正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中&#xff0…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

均衡后的SNRSINR

本文主要摘自参考文献中的前两篇&#xff0c;相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程&#xff0c;其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt​ 根发送天线&#xff0c; n r n_r nr​ 根接收天线的 MIMO 系…...