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

【c数据结构】OJ练习篇 帮你更深层次理解链表!(相交链表、相交链表、环形链表、环形链表之寻找环形入口点、判断链表是否是回文结构、 随机链表的复制)

目录

一. 相交链表

二. 环形链表

三. 环形链表之寻找环形入口点

四. 判断链表是否是回文结构

五. 随机链表的复制


一. 相交链表

最简单粗暴的思路,遍历两个链表,分别寻找是否有相同的对应的结点。

  1. 我们对两个链表的每个对应的节点进行判断比较,如果不相等的话

  2. 那么我们就进行换下一对节点进行判断

但这里存在一个弊端,两条链表可能有一条长,一条短,存在节点数不一样的情况,挨个比较。

举例来说,只是举例来说:

  • 假设一个链表是6个节点,一个是8个节点,那么差值就是8

  • 那么我们让长的那个链表优先走 | 8-6 | 步,走后两个链表长度一致,就能开始进行比较了

  • 解决这个问题很简单--> 遍历计算两个链表长度求差,让长的先走完差值步,使两条链表长度一致。 

于是思路有,步骤有√

  1. 求差求两个链表长度差值
  2. 让长的链表先走差值步
  3.  遍历两个链表,分别对应是否指向相同的结点
/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {//1. 遍历两个链表,求他们的长度差//设置两个链表头结点,方便遍历ListNode* l1 = headA;ListNode* l2 = headB;//设置变量存放链表长度,方便求差int sizeA=0,sizeB=0;//遍历计算两条链表长度ingwhile(l1){sizeA++;l1 = l1->next;}while(l2){sizeB++;l2 = l2->next;}//求长度差int gap = abs(sizeA-sizeB);//abs 绝对值函数//2.长链表先走长度差步//由于不知道哪个链表长,先随便定义再判断ListNode* longList = headB;ListNode* shortList = headA;if(sizeA > sizeB){longList = headA;shortList = headB;}//长链表先走while(gap--){longList = longList->next;}//此时的longList和shortList在同一起跑线//3. 遍历两个链表,要么相交,要么不相交while(longList && shortList)//条件是两个链表都不得是空{if(longList == shortList)//找到相同结点,相交{return longList;//反正相同结点,返回long 和short 都一样}//不相同,换下一结点继续比较longList = longList->next;shortList = shortList->next;}return NULL;//循环结束,可见不相交,返回空}

二. 环形链表

类似追击问题,若快指针在追慢指针的时候追到了,说明链表带环

 

如果链表不是带环的,那么快慢指针是绝对不会相遇的
/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {//创建快慢指针ListNode* slow = head;ListNode* fast = head;while(fast && fast->next){//慢指针走一步,快指针走两步,相当于快在一步一步追慢slow = slow ->next;fast = fast ->next->next;//相遇,说明带环if(fast == slow){return true;}}return false;
}

三. 环形链表之寻找环形入口点

假设meet为快慢指针相遇点

 

遍历头结点pcur和meet,因为环形,终将相遇
/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) {//1. 找快慢指针相遇点->说明是环形结点ListNode* slow = head;ListNode* fast = head;while(fast && fast ->next){slow = slow ->next;fast = fast ->next->next;if(fast == slow)//找到相遇点!是环形{//2. 遍历头结点和快慢指针相遇点,每次一步,其相遇点就是环形入环第一个结点ListNode* pcur = head; //定义头结点while(pcur != fast){//但凡是环形,肯定会相遇pcur = pcur ->next;fast = fast ->next;}return pcur;}}return NULL;
}

四. 判断链表是否是回文结构

 

先找中间结点(快慢指针)
再将中间结点之后的链表反转,最后链表左右进行比较看是否相同
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:bool chkPalindrome(ListNode* A) {//1. 找中间结点ListNode* slow = A;ListNode* fast = A;while(fast &&fast->next){slow = slow->next;fast = fast->next->next;}ListNode* mid = slow;//2. 根据中间结点反转后面的链表ListNode* n1 = NULL;//指向空ListNode* n2 = mid;//指向中间结点ListNode* n3 = n2->next;//指向n2的下一个结点while(n2){n2->next = n1;//n2指向其前一个结点(初始是空)n1 = n2;//n1往后走n2 = n3;//n2往后走if(n3)//前提:n3不得为空,n3才能继续往后走n3 = n3->next;//n3往后走}ListNode* right =n1;//n1为我反转链表的头结点//3. 比较原链表和反转链表的结点ListNode* left = A;//原链表头结点while(right)//反转链表的尾结点是指向空的,当其走到空,说明遍历完了{if(left->val != right->val){//有不相等的值,说明不回文return false;}left = left->next;right = right->next;}return true;}
};

五. 随机链表的复制

思路:

原链表上复制并插入复制结点

赋值random

断开链表

/*** Definition for a Node.* struct Node {*     int val;*     struct Node *next;*     struct Node *random;* };*/
typedef struct Node Node;
//复制链表结点
Node* buynode(int x){Node* newnode = (Node*)malloc(sizeof(Node));newnode->val = x;newnode->next = newnode->random = NULL;return newnode;
}
//将复制的新链表插入原链表
void AddNode(Node* head){Node* pcur = head;//头结点while(pcur){Node* Next = pcur->next;//原链表的下一结点Node* newnode = buynode(pcur->val);//要复制的新结点newnode->next = Next;pcur->next = newnode;pcur = Next;//pcur走到下一结点}}struct Node* copyRandomList(struct Node* head) {if(head == NULL){return NULL;}//1. 原链表上复制结点//此时链表是 node1 -> newcopy1 -> node2 -> newcopy2-> node3..AddNode(head);//2. 赋值randomNode* pcur = head;while(pcur){//循环修改random指针Node* copy = pcur->next;//此时pcur的下一结点即上一步插入的复制结点if(pcur->random != NULL){//因为创建新的节点时,直接让random指向空,现在只需将原链表中random不指向空的进行处理copy->random = pcur->random->next;}pcur = copy->next;//copy下一结点为原链表的下一结点}//3. 断开链表pcur = head;//让pcur回到头结点Node* newhead,*newtail;//为新链表创建头结点和要遍历连接的结点newhead = newtail = pcur->next;//pcur下一结点就是复制的新链表的头结点while(pcur->next->next)//因为有多插入复制的,所以pcur->next->next才是原链表下一结点{pcur = pcur->next->next;//pcur走到原链表下一结点newtail->next = pcur->next;//新链表连接新链表(被复制的)下一结点newtail = newtail->next;//新链表往后走}return newhead;//返回新链表头结点
}

 希望对你有帮助

相关文章:

【c数据结构】OJ练习篇 帮你更深层次理解链表!(相交链表、相交链表、环形链表、环形链表之寻找环形入口点、判断链表是否是回文结构、 随机链表的复制)

目录 一. 相交链表 二. 环形链表 三. 环形链表之寻找环形入口点 四. 判断链表是否是回文结构 五. 随机链表的复制 一. 相交链表 最简单粗暴的思路,遍历两个链表,分别寻找是否有相同的对应的结点。 我们对两个链表的每个对应的节点进行判断比较&…...

微软开源GraphRAG的使用教程(最全,非常详细)

GraphRAG的介绍 目前微软已经开源了GraphRAG的完整项目代码。对于某一些LLM的下游任务则可以使用GraphRAG去增强自己业务的RAG的表现。项目给出了两种使用方式: 在打包好的项目状态下运行,可进行尝试使用。在源码基础上运行,适合为了下游任…...

使用Refine构建项目(1)初始化项目

要初始化一个空的Refine项目,你可以使用Refine提供的CLI工具create-refine-app。以下是初始化步骤: 使用npx命令: 在命令行中运行以下命令来创建一个新的Refine项目: npx create-refine-applatest my-refine-project这将引导你通过…...

【Docker】安装及使用

1. 安装Docker Desktop Docker Desktop是官方提供的桌面版Docker客户端,在Mac上使用Docker需要安装这个工具。 访问 Docker官方页面 并下载Docker Desktop for Mac。打开下载的.dmg文件,并拖动Docker图标到应用程序文件夹。安装完成后,打开…...

[大语言模型-论文精读] 以《黑神话:悟空》为研究案例探讨VLMs能否玩动作角色扮演游戏?

1. 论文简介 论文《Can VLMs Play Action Role-Playing Games? Take Black Myth Wukong as a Study Case》是阿里巴巴集团的Peng Chen、Pi Bu、Jun Song和Yuan Gao,在2024.09.19提交到arXiv上的研究论文。 论文: https://arxiv.org/abs/2409.12889代码和数据: h…...

提升动态数据查询效率:应对数据库成为性能瓶颈的优化方案

引言 在现代软件系统中,数据库性能是决定整个系统响应速度和处理能力的关键因素之一。然而,当系统负载增加,特别是在高并发、大数据量场景下,数据库性能往往会成为瓶颈,导致查询响应时间延长,影响用户体验…...

Prometheus+grafana+kafka_exporter监控kafka运行情况

使用Prometheus、Grafana和kafka_exporter来监控Kafka的运行情况是一种常见且有效的方案。以下是详细的步骤和说明: 1. 部署kafka_exporter 步骤: 从GitHub下载kafka_exporter的最新版本:kafka_exporter项目地址(注意&#xff…...

在vue中:style 的几种使用方式

在日常开发中:style的使用也是比较常见的&#xff1a; 亲测有效 1.最通用的写法 <p :style"{fontFamily:arr.conFontFamily,color:arr.conFontColor,backgroundColor:arr.conBgColor}">{{con.title}}</p> 2.三元表达式 <a :style"{height:…...

商城小程序后端开发实践中出现的问题及其解决方法

前言 商城小程序后端开发中&#xff0c;开发者可能会面临多种问题。以下是一些常见的问题及其解决方法&#xff1a; 一、性能优化 问题&#xff1a;随着用户量的增加和功能的扩展&#xff0c;商城小程序可能会出现响应速度慢、处理效率低的问题。 解决方法&#xff1a; 对数…...

阿里Arthas-Java诊断工具,基本操作和命令使用

Arthas 是阿里巴巴开源的一款Java诊断工具&#xff0c;深受开发者喜爱。它可以帮助开发者在不需要修改代码的情况下&#xff0c;对运行中的Java程序进行问题诊断和性能分析。 软件具体使用方法 1 启动 Arthas&#xff0c;此时可能会出现好几个jvm的进程号&#xff0c;输入序号…...

Go 1.19.4 路径和目录-Day 15

1. 路径介绍 存储设备保存着数据&#xff0c;但是得有一种方便的模式让用户可以定位资源位置&#xff0c;操作系统采用一种路径字符 串的表达方式&#xff0c;这是一棵倒置的层级目录树&#xff0c;从根开始。 相对路径&#xff1a;不是以根目录开始的路径&#xff0c;例如 a/b…...

jEasyUI 创建标签页

jEasyUI 创建标签页 jEasyUI&#xff08;jQuery EasyUI&#xff09;是一个基于jQuery的框架&#xff0c;它为Web应用程序提供了丰富的用户界面组件。标签页&#xff08;Tabs&#xff09;是jEasyUI中的一个常用组件&#xff0c;用于在一个页面内组织多个面板&#xff0c;用户可…...

鸿蒙HarmonyOS开发:一次开发,多端部署(界面级)天气应用案例

文章目录 一、布局简介二、典型布局场景三、侧边栏 SideBarContainer1、子组件2、属性3、事件 四、案例 天气应用1、UX设计2、实现分析3、主页整体实现4、具体代码 五、运行效果 一、布局简介 布局可以分为自适应布局和响应式布局&#xff0c;二者的介绍如下表所示。 名称简介…...

使用 Python 模拟光的折射,反射,和全反射

✅作者简介&#xff1a;2022年博客新星 第八。热爱国学的Java后端开发者&#xff0c;修心和技术同步精进。 &#x1f34e;个人主页&#xff1a;Java Fans的博客 &#x1f34a;个人信条&#xff1a;不迁怒&#xff0c;不贰过。小知识&#xff0c;大智慧。 &#x1f49e;当前专栏…...

大厂太卷了!又一款国产AI视频工具上线了,免费无限使用!(附提示词宝典)

大家好&#xff0c;我是程序员X小鹿&#xff0c;前互联网大厂程序员&#xff0c;自由职业2年&#xff0c;也一名 AIGC 爱好者&#xff0c;持续分享更多前沿的「AI 工具」和「AI副业玩法」&#xff0c;欢迎一起交流~ 记得去年刚开始分享 AI 视频工具的时候&#xff0c;介绍的大多…...

vue3扩展echart封装为组件库-快速复用

ECharts ECharts&#xff0c;全称Enterprise Charts&#xff0c;是一款由百度团队开发并开源&#xff0c;后捐赠给Apache基金会的纯JavaScript图表库。它提供了直观、生动、可交互、可个性化定制的数据可视化图表&#xff0c;广泛应用于数据分析、商业智能、网页开发等领域。以…...

随机掉落的项目足迹:Vue3 + wangEditor5富文本编辑器——toolbar.getConfig() 查看工具栏的默认配置

问题引入 小提示&#xff1a;问题引入是一个讲故事的废话环节&#xff0c;各位小伙伴可以直接跳到第二大点&#xff1a;问题解决 我的项目不需要在富文本编辑器中引入添加代码块的功能&#xff0c;于是我寻思在工具栏上把操作代码的菜单删一删 于是我来到官网文档工具栏配置 …...

更新 Git 软件

更新 Git 软件本身是指将你当前安装的 Git 版本升级到最新版本。不同的操作系统有不同的更新方法。以下是针对 Windows、macOS 和 Linux 的 Git 更新步骤&#xff1a; Windows 检查当前版本&#xff1a; git --version访问官网下载最新版本&#xff1a; 访问 Git 官方网站 (ht…...

Keil根据map文件确定单片机代码存储占用flash情况

可以从map文件中查看得知&#xff0c;代码占用内存情况大概为35KB,而在在线仿真时&#xff0c;可以看到在flash的0x8008F64地址前均有数据&#xff0c;是代码数据&#xff0c;8F64(HEX)36708(DEC),36708/102335,刚好35。因此&#xff0c;要想操作读写flash&#xff0c;必须在不…...

ByteTrack多目标跟踪流程图

ByteTrack多目标跟踪流程图 点个赞吧&#xff0c;谢谢。...

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

<6>-MySQL表的增删查改

目录 一&#xff0c;create&#xff08;创建表&#xff09; 二&#xff0c;retrieve&#xff08;查询表&#xff09; 1&#xff0c;select列 2&#xff0c;where条件 三&#xff0c;update&#xff08;更新表&#xff09; 四&#xff0c;delete&#xff08;删除表&#xf…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

Rapidio门铃消息FIFO溢出机制

关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系&#xff0c;以下是深入解析&#xff1a; 门铃FIFO溢出的本质 在RapidIO系统中&#xff0c;门铃消息FIFO是硬件控制器内部的缓冲区&#xff0c;用于临时存储接收到的门铃消息&#xff08;Doorbell Message&#xff09;。…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问&#xff08;基础概念问题&#xff09; 1. 请解释Spring框架的核心容器是什么&#xff1f;它在Spring中起到什么作用&#xff1f; Spring框架的核心容器是IoC容器&#…...

关于uniapp展示PDF的解决方案

在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项&#xff1a; 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库&#xff1a; npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...

LangChain 中的文档加载器(Loader)与文本切分器(Splitter)详解《二》

&#x1f9e0; LangChain 中 TextSplitter 的使用详解&#xff1a;从基础到进阶&#xff08;附代码&#xff09; 一、前言 在处理大规模文本数据时&#xff0c;特别是在构建知识库或进行大模型训练与推理时&#xff0c;文本切分&#xff08;Text Splitting&#xff09; 是一个…...

AxureRP-Pro-Beta-Setup_114413.exe (6.0.0.2887)

Name&#xff1a;3ddown Serial&#xff1a;FiCGEezgdGoYILo8U/2MFyCWj0jZoJc/sziRRj2/ENvtEq7w1RH97k5MWctqVHA 注册用户名&#xff1a;Axure 序列号&#xff1a;8t3Yk/zu4cX601/seX6wBZgYRVj/lkC2PICCdO4sFKCCLx8mcCnccoylVb40lP...