链表一：寻找环形链表的入口点-程序员宅基地
技术标签： 单链表 剑指offer&&个人总结 数据结构
寻找环形链表的入口点
环形链表的入口点
1.首先怎么判断链表是否有环
寻找环形链表入口点的第一步，要先判断该链表是否为环形链表，环形链表的尾指针指向的位置是不确定的，它可以在任何位置成环。
如下面这些图所示：
那么如何判断是否有环呢？我们可以采用双指针法，思路如下：
具体地，我们定义两个指针，一快一满。慢指针每次只移动一步，而快指针每次移动两步。初始时，快、慢指针在位置 head。这样一来，如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表。
代码如下：
bool hasCycle(struct ListNode *head)
{
struct ListNode *slow=head; //慢指针
struct ListNode *fast=head; //快指针
//慢指针一次走一步，快指针一次走两步
while(fast!=NULL&&fast->next!=NULL)
{
slow=slow->next;
fast=fast->next->next;
if(slow==fast)
{
return true;
}
}
return false;
}
对于以上代码我们难免会提出以下两个问题；
（1）为什么slow走一步，fast走两步，他们一定会在环里面相遇，会不会永远追不上?请证明！
答：
不会追不上。假设slow进环的时候，fast与slow的距离是N，紧接着追击的过程中（fast追slow）fast向前走两步，slow走一步，他们每次一走，它们之间的距离就会缩小1，由一开始相距N，到后面相距0。
最终fast与slow会在相遇点相遇
（2）slow走一步，fast走3步？走4步？走x步行不行？为什么？请证明！
此时我们就可以发现要发生相遇与fast走的步数和环中的节点数有关。
我们设fast走X步，环中结点数为Y
2.找入环点
经过上图我们分析我们可以写出如下代码：
struct ListNode *detectCycle(struct ListNode *head)
{
struct ListNode* slow = head; //慢指针
struct ListNode* fast = head; //快指针
//慢指针一次走一步，快指针一次走两步
while (fast != NULL && fast->next != NULL)
{
slow = slow->next;
fast = fast->next->next;
if (slow == fast)
{
//相遇结点
struct ListNode*meet=fast;
while(meet!=head)
{
meet=meet->next;
head=head->next;
}
return meet;
}
}
return NULL;
}
智能推荐
单目双目标定_生成棋盘格每个内角点的空间三维左边-程序员宅基地
文章浏览阅读587次。本文用QT调用OpenCV4.5.1进行相机标定。头文件如下#include <QMainWindow>#include <opencv2/opencv.hpp>#include <iostream>#include <math.h>#include <fstream>#include <vector>using namespace cv;using namespace std;1.进行摄像机的读取，用O._生成棋盘格每个内角点的空间三维左边
cxp文件查看 欧姆龙_cxp格式怎么打开-程序员宅基地
文章浏览阅读1.9k次。cxp格式怎么打开cxp是一种Core Media Player XML-based Playlist 文件，可以用CAXA工艺图表或CX-P5.0打开。北京数码大方科技股份有限公司(CAXA)是中国领先的工业软件和服务公司，是中国最大的CAD和PLM软件供应商，是中国工业云的倡导者和领跑者。主要提供数字化设计(CAD)、数字化制造(MES)、产品全生命周期管理(PLM)和工业云服务，是“中国工业..._cxp 文件
码云WebHook使用_码云 webhook 在哪里-程序员宅基地
文章浏览阅读666次。服务器配置gitee，webhook钩子_码云 webhook 在哪里
python安装教程_pydes安装-程序员宅基地
文章浏览阅读672次。第一步：下载Python安装包在相关浏览器访问Python的官网 中找到适合自己需求Python安装包版本，_pydes安装
【Flink】 FLink TaskManager with id is no longer reachable-程序员宅基地
文章浏览阅读2.4k次。flink报错如下看起来是心跳的原因，为什么会丢失心跳呢？部署在k8s里面，taskmanger还是自己挂了又重启了，具体taskmanger的问题还在定位根据报错找到对应的源码@Override@Override@Override@Override这里报错的id是?resourceId在方法getTaskManagerResourceID 中我们可以看到这个id是如何生成的。地址和rpcPort?_is no longer reachable
Android TEE可信计算环境与TrustZone基础_secure spi-程序员宅基地
文章浏览阅读2.1k次，点赞2次，收藏19次。本文介绍了可信计算的基本概念、可信计算环境（TEE）的产生和应用，并详细介绍了 Android 移动端基于 TrustZone 架构实现的 TEE 的框架设计、安全机制等。_secure spi
随便推点
伽马校正笔记（Gamma Correction）_伽马曲线-程序员宅基地
文章浏览阅读3.2k次，点赞3次，收藏18次。在数字图像系统中，伽马（Gamma）是一个重要的但很少被正确理解的特性。它定义了一个像素的数值和对应的实际亮度之间的关系。_伽马曲线
java爬虫黑马百度云,Java爬虫小Demo java爬取百度风云榜数据-程序员宅基地
文章浏览阅读189次。Java爬虫小Demo java爬取百度风云榜数据 很简单的一个小例子，使用到了java的爬虫框架jsoup ，一起啦看看实现的方法吧！相关推荐：Python爬虫实战 python爬虫爬取百度风云榜榜单信息Pom文件插入依赖的引用：org.jsoupjsoup1.12.1实现方法代码：public String spider() {String url = "http://top.baidu.c..._java 黑马爬虫demo
vue项目中使用lib-flexible解决移动端适配的问题_uniapp lib-flexible-程序员宅基地
文章浏览阅读1.2w次。前言：先说下为什么使用 lib-flexible为了解决移动端适配问题，更多参考：https://www.cnblogs.com/lyzg/p/5058356.html动态改写标签给元素添加data-dpr属性，并且动态改写data-dpr的值给元素添加font-size属性，并且动态改写font-size的值1: 效果（效果更直观）添加lib-flexible前效果（页面不会随视..._uniapp lib-flexible
java爬虫与python爬虫的区别_java爬虫和python爬虫哪个好-程序员宅基地
文章浏览阅读6k次。python优点：1.各种爬虫框架，方便高效的下载网页;2.多线程、进程模型成熟稳定，爬虫是一个典型的多任务处理场景，请求页面时会有较长的延迟，总体来说更多的是等待。多线程或进程会更优化程序效率，提升整个系统下载和分析能力。3.gae 的支持，当初写爬虫的时候刚刚有 gae，而且只支持 python ，利用 gae 创建的爬虫几乎免费，最多的时候我有近千个应用实例在工作。java 和 c++ ：相..._爬虫java还是hipython
一次搞懂Java如何调用Kotlin的高级特性_java调用kotlin方法-程序员宅基地
文章浏览阅读3.4k次。虽然 Kotlin 推出很多年了，但是在国内的普及度并没有成压倒性优势，还是有很多新老项目使用Java语言开发的。（Java永不为奴 :sweat_smile::sweat_smile:）如果项目中其他小伙伴使用的Kotlin，而我只会Java，那我怎么调用他Kotlin的方法？其实Kotlin早给我们做好了兼容，很多特性我们都可以使用Java来调用。下面一起看看一些常用的Kotlin特性如何使用Java语言来调用。一、Java调用KT属性与方法Kotlin的属性与方法，在Java中的调用。_java调用kotlin方法
一维条形码 code128 的全面介绍_code128条形码-程序员宅基地
文章浏览阅读2.5w次，点赞6次，收藏23次。0：code128，编码格式：Code128A字符集 包括大写字母、数字、常用标点符号和一些控制符。Code128B字符集 包括大小写字母、数字、常用标点符号。Code128C字符集 为纯数字序列。Code128Auto 是将上述三种字符集最佳优化组合。1：Code128编码规则：开始位 ＋ ［FNC1(为EAN128码时加)］ ＋ 数据位 _code128条形码