【c数据结构】OJ练习篇 帮你更深层次理解链表!(相交链表、相交链表、环形链表、环形链表之寻找环形入口点、判断链表是否是回文结构、 随机链表的复制)
目录
一. 相交链表
二. 环形链表
三. 环形链表之寻找环形入口点
四. 判断链表是否是回文结构
五. 随机链表的复制
一. 相交链表
最简单粗暴的思路,遍历两个链表,分别寻找是否有相同的对应的结点。
-
我们对两个链表的每个对应的节点进行判断比较,如果不相等的话
-
那么我们就进行换下一对节点进行判断
但这里存在一个弊端,两条链表可能有一条长,一条短,存在节点数不一样的情况,挨个比较。
举例来说,只是举例来说:
假设一个链表是6个节点,一个是8个节点,那么差值就是8
那么我们让长的那个链表优先走 | 8-6 | 步,走后两个链表长度一致,就能开始进行比较了
解决这个问题很简单--> 遍历计算两个链表长度求差,让长的先走完差值步,使两条链表长度一致。
于是思路有,步骤有√
- 求差求两个链表长度差值
- 让长的链表先走差值步
- 遍历两个链表,分别对应是否指向相同的结点
/*** 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;
}
三. 环形链表之寻找环形入口点


/*** 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项目地址(注意ÿ…...

在vue中:style 的几种使用方式
在日常开发中:style的使用也是比较常见的: 亲测有效 1.最通用的写法 <p :style"{fontFamily:arr.conFontFamily,color:arr.conFontColor,backgroundColor:arr.conBgColor}">{{con.title}}</p> 2.三元表达式 <a :style"{height:…...
商城小程序后端开发实践中出现的问题及其解决方法
前言 商城小程序后端开发中,开发者可能会面临多种问题。以下是一些常见的问题及其解决方法: 一、性能优化 问题:随着用户量的增加和功能的扩展,商城小程序可能会出现响应速度慢、处理效率低的问题。 解决方法: 对数…...
阿里Arthas-Java诊断工具,基本操作和命令使用
Arthas 是阿里巴巴开源的一款Java诊断工具,深受开发者喜爱。它可以帮助开发者在不需要修改代码的情况下,对运行中的Java程序进行问题诊断和性能分析。 软件具体使用方法 1 启动 Arthas,此时可能会出现好几个jvm的进程号,输入序号…...

Go 1.19.4 路径和目录-Day 15
1. 路径介绍 存储设备保存着数据,但是得有一种方便的模式让用户可以定位资源位置,操作系统采用一种路径字符 串的表达方式,这是一棵倒置的层级目录树,从根开始。 相对路径:不是以根目录开始的路径,例如 a/b…...
jEasyUI 创建标签页
jEasyUI 创建标签页 jEasyUI(jQuery EasyUI)是一个基于jQuery的框架,它为Web应用程序提供了丰富的用户界面组件。标签页(Tabs)是jEasyUI中的一个常用组件,用于在一个页面内组织多个面板,用户可…...

鸿蒙HarmonyOS开发:一次开发,多端部署(界面级)天气应用案例
文章目录 一、布局简介二、典型布局场景三、侧边栏 SideBarContainer1、子组件2、属性3、事件 四、案例 天气应用1、UX设计2、实现分析3、主页整体实现4、具体代码 五、运行效果 一、布局简介 布局可以分为自适应布局和响应式布局,二者的介绍如下表所示。 名称简介…...

使用 Python 模拟光的折射,反射,和全反射
✅作者简介:2022年博客新星 第八。热爱国学的Java后端开发者,修心和技术同步精进。 🍎个人主页:Java Fans的博客 🍊个人信条:不迁怒,不贰过。小知识,大智慧。 💞当前专栏…...

大厂太卷了!又一款国产AI视频工具上线了,免费无限使用!(附提示词宝典)
大家好,我是程序员X小鹿,前互联网大厂程序员,自由职业2年,也一名 AIGC 爱好者,持续分享更多前沿的「AI 工具」和「AI副业玩法」,欢迎一起交流~ 记得去年刚开始分享 AI 视频工具的时候,介绍的大多…...

vue3扩展echart封装为组件库-快速复用
ECharts ECharts,全称Enterprise Charts,是一款由百度团队开发并开源,后捐赠给Apache基金会的纯JavaScript图表库。它提供了直观、生动、可交互、可个性化定制的数据可视化图表,广泛应用于数据分析、商业智能、网页开发等领域。以…...

随机掉落的项目足迹:Vue3 + wangEditor5富文本编辑器——toolbar.getConfig() 查看工具栏的默认配置
问题引入 小提示:问题引入是一个讲故事的废话环节,各位小伙伴可以直接跳到第二大点:问题解决 我的项目不需要在富文本编辑器中引入添加代码块的功能,于是我寻思在工具栏上把操作代码的菜单删一删 于是我来到官网文档工具栏配置 …...
更新 Git 软件
更新 Git 软件本身是指将你当前安装的 Git 版本升级到最新版本。不同的操作系统有不同的更新方法。以下是针对 Windows、macOS 和 Linux 的 Git 更新步骤: Windows 检查当前版本: git --version访问官网下载最新版本: 访问 Git 官方网站 (ht…...

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

ByteTrack多目标跟踪流程图
ByteTrack多目标跟踪流程图 点个赞吧,谢谢。...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析
这门怎么题库答案不全啊日 来简单学一下子来 一、选择题(可多选) 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘:专注于发现数据中…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端
🌟 什么是 MCP? 模型控制协议 (MCP) 是一种创新的协议,旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议,它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

DAY 47
三、通道注意力 3.1 通道注意力的定义 # 新增:通道注意力模块(SE模块) class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例
文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...
【算法训练营Day07】字符串part1
文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接:344. 反转字符串 双指针法,两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...
Caliper 配置文件解析:config.yaml
Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

LLMs 系列实操科普(1)
写在前面: 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容,原视频时长 ~130 分钟,以实操演示主流的一些 LLMs 的使用,由于涉及到实操,实际上并不适合以文字整理,但还是决定尽量整理一份笔…...
c# 局部函数 定义、功能与示例
C# 局部函数:定义、功能与示例 1. 定义与功能 局部函数(Local Function)是嵌套在另一个方法内部的私有方法,仅在包含它的方法内可见。 • 作用:封装仅用于当前方法的逻辑,避免污染类作用域,提升…...

恶补电源:1.电桥
一、元器件的选择 搜索并选择电桥,再multisim中选择FWB,就有各种型号的电桥: 电桥是用来干嘛的呢? 它是一个由四个二极管搭成的“桥梁”形状的电路,用来把交流电(AC)变成直流电(DC)。…...