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

【链表OJ】相交链表 环形链表1

前言: 

💥🎈个人主页:​​​​​​Dream_Chaser~ 🎈💥

✨✨刷题专栏:http://t.csdn.cn/UlvTc

⛳⛳本篇内容:力扣上链表OJ题目

目录

一.leetcode 160. 相交链表

1.问题描述:

2.解题思路:

二.leetcode 141.环形链表

1.问题描述:

2.代码思路:

3.问题证明:


一.leetcode 160. 相交链表

来源:160. 相交链表 - 力扣(LeetCode)

1.问题描述:

给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回NULL 。

图示两个链表在节点c1开始相交

已知a1与b1的头结点地址,并分别用headA和headB指针指向

  • 题目数据 保证 整个链式结构中不存在环。
  • 注意,函数返回结果后,链表必须 保持其原始结构 。

题目接口:

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) 
{}

2.解题思路:

原始链表:

  • 首先定义tailAtailB分别遍历a链表b链表,在遍历过程中,分别求出两链表长度,分别定义为lenA和lenB,然后用lenA和lenB相减取差的绝对值,计为差距步gap

  • 然后定义指向长链表的指针longList,和指向短链表的指针shortList,用前面定义的LenALenB比较它们的长度,进行合适赋值,接着让长的链表走差距步gap。若长链表结点的地址不等于短链表,则让tailA和tailB指针继续走,有相等结点则跳出循环,返回此时的longList或者shortList

 实现代码:

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) 
{struct ListNode* tailA = headA;struct ListNode* tailB = headB;int lenA = 1, lenB = 1;//原始长度定义为1才是正确的while (tailA){tailA = tailA->next;lenA++;}while (tailB){tailB = tailB->next;lenB++;}if (tailA != tailB)//若两指针到结束也找不到相等结点,则返回NULLreturn NULL;int gap = abs(lenA - lenB);//取出两者相减的绝对值,赋值给gap表示两链表的差距步struct ListNode*longList = headA;//先假定A链表为长链表struct ListNode* shortList = headB;if (lenA < lenB)//接着两链表比较,如果满足此条件,则重新赋值,定义B链表的为长链表{longList = headB;shortList = headA;}while (gap--)//长链表先走差距步{longList = longList->next;}while (longList != shortList)//若没有相等(地址相等)则继续遍历{longList = longList->next;shortList = shortList->next;}return shortList;
}

代码执行:

二.leetcode 141.环形链表

1.问题描述:

给你一个链表的头节点 head ,判断链表中是否有环。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ,则返回 true 。 否则,返回 false 

题解接口:

bool hasCycle(struct ListNode *head) {}

2.代码思路:

本题的代码思路:

定义一个快指针,让其先走两步,接着定义一个慢指针,一次走一步,反复此循环。

  • 如果快慢指针指向的地址相等,则证明链表中存在环。
  • 如果快指针提前指向NULL,循环结束,则证明不是环形链表,直接返回false。

函数实现

bool hasCycle(struct ListNode *head) {struct ListNode* fast=head,*slow =head;while(fast && fast->next){fast=fast->next->next;//快指针先走两步,慢指针走一步slow=slow->next; //慢指针走一步if(fast==slow)//指针相遇表明链表带环{return true;}}return false;//否则返回NULL
}

代码执行:

然而本题的重点在于如何证明上面的代码的实现逻辑,是一个数学问题。

3.问题证明:

1、slow和fast一定会相遇吗?

答:一定会

画一张图来证明一下, 此时两指针同时指向头节点的地址。

 接着先让快指针fast=fast->next->next(快指针先走两步),后让 slow=slow->next(慢指针走一步).

fast会先进环,slow会后进环,假设slow进环时,slow和fast之间的距离为N

slow进环以后,fast开始追击slow,slow每走1步,fast每走2步他们之间距离缩小1

2、slow走1步,fast走n(3/4/5….)步可以吗?(n > 2) 

 不一定

举例:

slow每次走步,fast每次走步,它们一定可以相遇吗?答:不一定。

画图

当快慢指针之间的距离个数为奇数

fast会先进环,slow会后进环,假设slow进环时, slow和fast之间的距离为N

slow进环以后,fast开始追击slow,slow每走1步,fast每走3步,他们之间距离缩小2

当快指针追赶上慢指针时,此时错过了,并进入新一轮的追击,假设一个值C为环的长度,那么快慢指针的距离此时必为C-1

所以,如果C-1是奇数那么fast永远追不上slow

当C-1的距离为偶数时,那么此时的距离变化为

N N-2 N-4 ... 4 2 0 ,0则表示此时两指针相遇,表明下一轮可以追上。

        本文结束,如有错误,我会继续更新关于链表oj的题目,欢迎大家指正!

相关文章:

【链表OJ】相交链表 环形链表1

前言: &#x1f4a5;&#x1f388;个人主页:​​​​​​Dream_Chaser&#xff5e; &#x1f388;&#x1f4a5; ✨✨刷题专栏:http://t.csdn.cn/UlvTc ⛳⛳本篇内容:力扣上链表OJ题目 目录 一.leetcode 160. 相交链表 1.问题描述: 2.解题思路: 二.leetcode 141.环形链表 …...

DevOps之自动化测试

什么是自动化测试&#xff1f; 明确一下自动化测试不是什么。自动化测试不是指自动化生成测试代码&#xff0c;而是自动化地执行由开发人员或测试人员编写的测试代码。正如下面这句谚语&#xff1a;“绝不要手工去做任何可以被自动化处理的事情。——Curt Hibbs” 之前是由人…...

Java 程序打印 OpenCV 的版本

我们可以使用 Java 程序来使用 OpenCV。 OpenCV 的使用需要动态库的加载才可以。 加载动态库 到 OpenCV 的官方网站上下载最新的发布版本。 Windows 下载的是一个可执行文件&#xff0c;没关系&#xff0c;这个可执行文件是一个自解压程序。 当你运行以后会提示你进行解压。…...

ChatGPT⼊门到精通(2):ChatGPT 能为我们做什么

⼀、雇佣免费的⼲活⼩弟 有了ChatGPT后&#xff0c;就好⽐你有了好⼏个帮你免费打⼯的「⼩弟」&#xff0c;他们可以帮你做很多 ⼯作。我简单总结⼀些我⽬前使⽤过的⽐较好的基于ChatGPT的服务和应⽤。 1、总结、分析 当我们在阅读⼀些⽂章和新闻的时候&#xff0c;有的⽂章写…...

线程和进程的区别是什么?

线程(Thread)和进程(Process)是操作系统中两个重要的概念,用于管理程序的执行。它们有以下区别: 定义:进程:进程是程序的一个执行实例,它包含了程序的代码、数据以及执行上下文。进程是操作系统分配资源和调度的基本单位。线程:线程是进程的子执行单元,一个进程可以…...

力扣27.移除元素

27. 移除元素 提示 简单 1.9K 相关企业 给你一个数组 nums 和一个值 val&#xff0c;你需要 原地 移除所有数值等于 val 的元素&#xff0c;并返回移除后数组的新长度。 不要使用额外的数组空间&#xff0c;你必须仅使用 O(1) 额外空间并 原地 修改输入数组。 元素的顺序…...

指针(个人学习笔记黑马学习)

1、指针的定义和使用 #include <iostream> using namespace std;int main() {int a 10;int* p;p &a;cout << "a的地址为&#xff1a;" << &a << endl;cout << "a的地址为&#xff1a;" << p << endl;…...

vue 路由动态加载

在 Vue.js 中&#xff0c;可以使用 webpack 的动态导入语法来实现路由动态加载。下面是一个简单的示例&#xff1a; const Home () > import(/* webpackChunkName: "home" */ ./views/Home.vue); const About () > import(/* webpackChunkName: "about…...

电脑识别不了固态硬盘怎么办?

在使用固态硬盘时&#xff0c;可能会出现电脑无法识别的情况&#xff0c;这时我们就无法使用固态硬盘中的数据。那么&#xff0c;电脑识别不了固态硬盘怎么办&#xff1f; 为什么电脑识别不了固态硬盘&#xff1f; 一般来说&#xff0c;电脑识别不了固态硬盘是因为以下3个原因…...

QCustomPlot 绘制卡顿问题

大数据量导致曲线绘制卡顿问题 这里提供一个思路在跟踪源码中发现底层卡顿在vector的resize() 此处扩容中 所以尽量使用下面的接口 /*! \overloadAdds the provided data point as \a key and \a value to the current data.Alternatively, you can also access and modify t…...

uni-app开发小程序,radio单选按钮,点击可以选中,再次点击可以取消

一、实现效果&#xff1a; 二、代码实现&#xff1a; 不适用官方的change方法&#xff0c;自己定义点击方法。 动态判断定义的值是否等于遍历的值进行回显&#xff0c;如果和上一次点击的值一样&#xff0c;就把定义的值改为null <template><view><radio-group&…...

【Qt专栏】实现单例程序,禁止程序多开的几种方式

目录 一&#xff0c;简要介绍 二&#xff0c;实现示例&#xff08;Windows&#xff09; 1.使用系统级别的互斥机制 2.通过共享内存&#xff08;进程间通信-IPC&#xff09; 3.使用命名互斥锁&#xff08;不推荐&#xff09; 4.使用文件锁 5.通过网络端口检测 一&#xf…...

力扣26. 删除有序数组中的重复项

给你一个 升序排列 的数组 nums &#xff0c;请你 原地 删除重复出现的元素&#xff0c;使每个元素 只出现一次 &#xff0c;返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。 考虑 nums 的唯一元素的数量为 k &#xff0c;你需要做…...

【机器学习】鸢尾花分类-逻辑回归示例

这段代码是一个完整的示例&#xff0c;展示了如何使用逻辑回归对鸢尾花数据集进行训练、保存模型&#xff0c;并允许用户输入数据进行预测。以下是对这段代码的总结&#xff1a;功能&#xff1a; 这段代码演示了如何使用逻辑回归对鸢尾花数据集进行训练&#xff0c;并将训练好的…...

Flink CDC介绍

1.CDC概述 CDC&#xff08;Change Data Capture&#xff09;是一种用于捕获和处理数据源中的变化的技术。它允许实时地监视数据库或数据流中发生的数据变动&#xff0c;并将这些变动抽取出来&#xff0c;以便进行进一步的处理和分析。 传统上&#xff0c;数据源的变化通常通过…...

Java集合sort排序报错UnsupportedOperationException处理

文章目录 报错场景排查解决UnmodifiableList类介绍 报错场景 我们使用的是PostgreSQL数据库&#xff0c;存储业务数据&#xff0c;业务代码使用的是Spring JPA我们做的是智慧交通信控平台&#xff0c;有个功能是查询展示区域的交通态势&#xff0c;需要按照不同维度排序展示区…...

安防监控/磁盘阵列存储/视频汇聚平台EasyCVR调用rtsp地址返回的IP不正确是什么原因?

安防监控/云存储/磁盘阵列存储/视频汇聚平台EasyCVR可拓展性强、视频能力灵活、部署轻快&#xff0c;可支持的主流标准协议有GB28181、RTSP/Onvif、RTMP等&#xff0c;以及厂家私有协议与SDK接入&#xff0c;包括海康Ehome、海大宇等设备的SDK等&#xff0c;能对外分发RTSP、RT…...

Spring boot开启定时任务

Cron表达式生成器 基于接口的方式 使用Scheduled 注解很方便&#xff0c;但缺点是当我们调整了执行周期的时候&#xff0c;需要重启应用才能生效&#xff0c;这多少有些不方便。为了达到实时生效的效果&#xff0c;那么可以使用接口来完成定时任务&#xff0c;统一将定时器信…...

package.json相关知识记录

一、相关字段 npm官方字段介绍 &#x1f367; bin   >   简单理解&#xff1a;指定命令的名称及路径   &#x1f349; 相当于想path中添加路径&#xff0c;局部安装是在./node_modules/.bin/&#xff0c;全局安装是在全局的bin目录   &#x1f349; bin指定的文件必须…...

VueRouter使用详解(5000字通关大全)

Vue Router是一个官方的路由管理器&#xff0c;它可以让我们在Vue应用中实现单页面应用&#xff08;SPA&#xff09;的效果&#xff0c;即通过改变URL而不刷新页面来显示不同的内容。Vue Router可以让我们定义多个路由&#xff0c;每个路由对应一个组件&#xff0c;当URL匹配到…...

设计模式和设计原则回顾

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

visual studio 2022更改主题为深色

visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中&#xff0c;选择 环境 -> 常规 &#xff0c;将其中的颜色主题改成深色 点击确定&#xff0c;更改完成...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

网络编程(UDP编程)

思维导图 UDP基础编程&#xff08;单播&#xff09; 1.流程图 服务器&#xff1a;短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...

ABAP设计模式之---“简单设计原则(Simple Design)”

“Simple Design”&#xff08;简单设计&#xff09;是软件开发中的一个重要理念&#xff0c;倡导以最简单的方式实现软件功能&#xff0c;以确保代码清晰易懂、易维护&#xff0c;并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计&#xff0c;遵循“让事情保…...